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

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

生物分子计算进展

由于生物分子在化学反应中具有高度的并行性和识别能力 ,使生物分子计算在解决组合优化问题中显示出巨大的优势。生物分子计算已成功地应用于计算哈密顿路径、最大集合以及逻辑运算中的SAT类问题等 NP完全问题。本文总结了生物分子计算的基本思想与计算方法、生物分子计算的应用与进展 ,并对生物分子计算的发展趋势作了评述。