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

Surface-based DNA algorithm for Hamiltonian path problem

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

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 Hamihonian 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.