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

DNA Algorithm to the Directed Shortest Hamilton Path Problem

作　　者：高琳[1] 马瑞年 许进[2] 

机构地区：[1]西安电子科技大学雷达信号处理国家重点实验室,陕西西安710071 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《系统工程与电子技术》2002年第8期102-105,共4页Systems Engineering and Electronics

基　　金：国家自然科学基金 (699710 18) ;陕西省自然科学基金 (2 0 0 1X0 5 )资助课题

摘　　要：首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。DNA computing is a novel method of computing and biochemistry. The DNA algorithm to the directed shortest Hamilton path problem is introduced. The vertex, weight and direction of the graph are encoded by DNA string. The problem is solved by the tube operation that performs the basic core processing and the extraction that makes the results visible. The innovation of the paper is that weight is represented by DNA string. On the basis of the experiment method of molecular biology, the algorithm is an effective method.\;

关 键 词：DNA算法 NP-完全问题 有向哈密尔顿最短路 分子生物计算方法 

分 类 号：Q819[生物学—生物工程]