计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (8): 48-51.DOI: 10.3778/j.issn.1002-8331.2010.08.014

• 研究、探讨 • 上一篇    下一篇

哈密尔顿回路问题的DNA表面计算模型

李朝鹏1,2,成 运1,李肯立2,周 旭3   

  1. 1.湖南人文科技学院 通信与控制工程系,湖南 娄底 417000
    2.湖南大学 计算机与通信学院,长沙 410082
    3.嘉兴学院 数学与信息学院,浙江 嘉兴 314001
  • 收稿日期:2009-08-20 修回日期:2009-12-29 出版日期:2010-03-11 发布日期:2010-03-11
  • 通讯作者: 李朝鹏

Surface-based DNA algorithm for Hamiltonian path problem

LI Zhao-peng1,2,CHENG Yun1,LI Ken-li2,ZHOU Xu2   

  1. 1.Dept. of Communication and Control Engineering,Hunan University of Humanities,Science and Technology,Loudi,Hunan 417000,China
    2.School of Computer and Communication,Hunan University,Changsha 410082,China
    3.College of Mathematics and Information Engineering,JiaXing University,Jiaxing,Zhejiang 314001,China
  • Received:2009-08-20 Revised:2009-12-29 Online:2010-03-11 Published:2010-03-11
  • Contact: LI Zhao-peng

摘要: 首次提出用DNA表面计算模型来解决无向图哈密尔顿回路问题。该模型基于哈密尔顿回路问题的解空间,将问题解空间的DNA分子固定在固体载体上,对其进行荧光标记,然后通过相应的生化反应筛选出哈密尔顿回路问题的所有解。与已有的哈密尔顿路径问题的其它模型相比,新模型具有错误率低,编码简易,读取方便等更好的性能。

Abstract: The paper innovatively presents a surface-based DNA algorithm for solving Hamiltonian circuit problem in a nondirectional graph.The model,based on the solution space of Hamiltonian problem,fixes the DNA molecules of solution space on the solid carrier,and fluorescence labels on them,and then gets all solutions of Hamiltonian circuit problem by certain biochemical actions.Compared with other models for Hamiltonian path problem,this model shows better performances on low rate of error,easily coding and conveniency to read.

中图分类号: