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) 

作者机构：Dept. of Control Science and Eng. Huazhong Univ. of Sci. and Technol. Wuhan 430074 China Coll. of Transportation Wuhan Univ. of Technology Wuhan 430063 China Dept. of Mathematics and Physics Anhui Univ. of Sci. and Technol. Huainan 232001 China 

出 版 物：《Progress in Natural Science:Materials International》 (自然科学进展·国际材料(英文))

年 卷 期：2005年第15卷第2期

页      面：86-89页

核心收录：

学科分类：0710[理学-生物学] 071010[理学-生物化学与分子生物学] 081704[工学-应用化学] 07[理学] 08[工学] 0817[工学-化学工程与技术] 

基　　金：SupportedbytheNationalNaturalScienceFoundationofChina (GrantNos.60 3 73 0 89and 3 0 3 70 3 5 6) 

主　　题：DNA computing DNA graph structure graph isomorphism 

摘      要：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.