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

DNA algorithm of Hamilton path problem based on finite automaton

作　　者：杨学庆[1,2] 柳重堪[3] 

机构地区：[1]北京航空航天大学数学.信息与行为教育部重点实验室 [2]北京航空航天大学理学院,北京100083 [3]北京航空航天大学理学院

出　　处：《计算机工程与应用》2007年第18期87-89,共3页Computer Engineering and Applications

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

关 键 词：DNA计算 有穷自动机 哈密顿路径问题 

分 类 号：TP384[自动化与计算机技术—计算机系统结构]