计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (18): 87-89.

• 学术探讨 • 上一篇    下一篇

哈密顿路径问题的一种基于有穷自动机的DNA算法

杨学庆1,2,柳重堪2   

  1. 1.北京航空航天大学 数学•信息与行为教育部重点实验室,北京 100083
    2.北京航空航天大学 理学院,北京 100083
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-06-21 发布日期:2007-06-21
  • 通讯作者: 杨学庆

DNA algorithm of Hamilton path problem based on finite automaton

YANG Xue-qing1,2,LIU Zhong-kan2   

  1. 1.Key Laboratory of Mathematics,Informatics and Behavioral Semantics,Ministry of Education,Beihang University,Beijing 100083,China
    2.School of Science,Beihang University,Beijing 100083,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-06-21 Published:2007-06-21
  • Contact: YANG Xue-qing

摘要: 提出了一种基于有穷自动机的解决哈密顿路径问题的DNA算法,将有穷自动机的状态用含有DNA限制性内切酶的识别位点的DNA双链分子来编码,通过限制性内切酶的生物化学反应来实现状态的转移。算法的创新之处在于用DNA计算模拟有穷自动机的运行过程中,保留了其经过的各个状态,以便最后筛选出经过各个顶点的路径。算法的优点是实验实现简易,大大减少所使用的DNA分子的数量。

Abstract: A DNA algorithm based on finite automaton to the Hamilton path problem is presented in this article.The states of the finite automaton are encoded by double strands which all comprises different recognition sites.The transition is represented by a double strand with segment encoding for the current state and another segment encoding the next state.The innovation of the paper is that it keeps the states that finite automaton run.The advantage of this method is it can efficiently reduce the amount of DNA molecule.