|
|||||
|
|
| Algorithm of graph isomorphism with three dimensional DNA graph structures | |
| 作者姓名： | LIU Guangwu YIN Zhixiang XU Jin DONG Yafei |
| 作者单位： | Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China;College of Transportation,Wuhan University of Technology,Wuhan 430063,China,Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China;Department of Mathematics and Physics,Anhui University of Science and Technology,Huainan 232001,China,Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China,Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China |
| 摘 要： | An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed 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. |
| 关 键 词： | DNA computing DNA graph structure graph isomorphism |
Algorithm of graph isomorphism with three dimensional DNA graph structures |
|
| LIU Guangwu,YIN Zhixiang,XU Jin,DONG Yafei.Algorithm of graph isomorphism with three dimensional DNA graph structures[J].Progress in Natural Science,2005,15(2):181-184. | |
| Authors: | Liu Guangwu YIN Zhixiang XU Jin DONG Yafei |
| Institution: | 1. Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China;College of Transportation,Wuhan University of Technology,Wuhan 430063,China 2. Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China;Department of Mathematics and Physics,Anhui University of Science and Technology,Huainan 232001,China 3. Department of Control Science and Engineering,Hua Zhong University of Science and Technology,Wuhan 430074,China |
| Abstract: | An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed 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 |
| 本文献已被 万方数据 等数据库收录！ | |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 | |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 | |