有向最短哈密尔顿路问题的DNA算法

摘要：

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribo nucleic acid)算法,将顶点、权值用DNA片段编码,边的方向通过顶点的编码获得.将这些 DNA片段放入溶液中进行生化反应,通过基本的生物操作及生物酶完成解的产生及最终解的分离.该算法的创新之处在于权值的设计,合理有效地用DNA序列表示权值的大小,以便于使用常规的生物分离方法进行最优路径的选择.依据分子生物学的实验方法,说明了所提算法是有效和可行的.

关键词：DNA计算、NP-完全问题、有向哈密尔顿最短路

所属期刊栏目：24

分类号：Q811.211(生物工程学(生物技术))

资助基金：国家自然科学基金69971018;陕西省自然科学基金2001X05

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：102-105