传递闭包问题的DNA计算

Authors：刘文君; 殷志祥

Source：电脑知识与技术, 2012, (28): 6771.

• DNA计算
• 传递闭包
• NP完全问题

DNA计算是计算机科学和分子生物学相互结合,相互渗透而产生的新计算模式,在解决一些复杂的问题上,尤其是NP—完全问题上具有一定的优势,提供了新的解决途径。首先介绍DNA计算的基本原理,其次详细介绍传递闭包问题的DNA算法,对图中顶点用DNA片段进行编码,将这些DNA片段放入溶液中进行生化反应,通过基本的生物操作及生物酶完成解的产生,并最终筛选出传递闭包问题的所有解。最后介绍DNA计算的研究和一些尚待解决的问题。

• Institution
  安徽理工大学