| Algorithm of graph isomorphism with threedimensional DNA graph structures |
| |
| 引用本文： | LIU Guangwu 1,2*,YIN Zhixiang 1,3,XU Jin1 and DONG Yafei1(1. Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China, 2. College of Transportation,Wuhan University of Technology,Wuhan 430063,China, 3. Department of Mathematics and Physics,Anhui University of Science and Technology,Huainan 232001,China). Algorithm of graph isomorphism with threedimensional DNA graph structures[J]. 自然科学进展(英文版), 2005, 0(2) |
| |
| 作者姓名： | LIU Guangwu 1 2* YIN Zhixiang 1 3 XU Jin1 and DONG Yafei1(1. Department of Control Science and Engineering Hua Zhong University of Science and Technology Wuhan 430074 China 2. College of Transportation Wuhan University of Technology Wuhan 430063 China 3. Department of Mathematics and Physics Anhui University of Science and Technology Huainan 232001 China) |
| |
| 作者单位： | 1. Department of Control Science and Engineering，Hua Zhong University of Science and Technology，Wuhan 430074，China; 2. College of Transportation，Wuhan University of Technology，Wuhan 430063，China; 3. Department of Mathematics and Physics，Anhui University of Science and Technology，Huainan 232001，China |
| |
| 基金项目： | SupportedbytheNationalNaturalScienceFoundationofChina (GrantNos.60 3 73 0 89and 3 0 3 70 3 5 6) |
| |
| 摘 要： | ResearchonDNAcomputingwasinitializedin1994 ,whenAdleman[1] proposedamethodofsolvingasmallinstanceoftheHamiltonianPathproblembyalaboratoryexperimentinvolvingDNAmolecules .Later,Lipton[2 ] demonstratedhowalargeclassofNP completeproblemscouldbesolvedbyencodingtheprobleminDNAmolecules .Inparticular ,LiptonshowedonefamousNP problem ,theso called“satisfiability”problem (SAT)andsubsequentlytheotherNP problemscouldbeencodedandsolvedusingmolecules .TheadvantagesofDNAcomputingareitsmassivepa…
|
Algorithm of graph isomorphism with threedimensional DNA graph structures |
| |
| LIU Guangwu ,,YIN Zhixiang ,,XU Jin and DONG Yafei. Algorithm of graph isomorphism with threedimensional DNA graph structures[J]. Progress in Natural Science, 2005, 0(2) |
| |
| Authors: | LIU Guangwu YIN Zhixiang XU Jin DONG Yafei |
| |
| Affiliation: | LIU Guangwu 1,2*,YIN Zhixiang 1,3,XU Jin1 and DONG Yafei1 |
| |
| Abstract: | An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The k-armed branched junction molecules are used to code k-degree vertices. Double stranded molecules are used to code edges. Then the molecules are mixed in a tube to be ligated. The result can be detected by gel electrophoresis. The time complexity of the algorithm is O(n2), where n is the number of vertices of the graph. |
| |
| Keywords: | DNA computing DNA graph structure graph isomorphism |
| 本文献已被 CNKI 等数据库收录！ |
