| 有向最短哈密尔顿路问题的DNA算法 |
| |
| 引用本文： | 高琳,马瑞年,许进.有向最短哈密尔顿路问题的DNA算法[J].系统工程与电子技术,2002,24(8):102-105. |
| |
| 作者姓名： | 高琳 马瑞年 许进 |
| |
| 作者单位： | 1. 西安电子科技大学雷达信号处理国家重点实验室,陕西,西安,710071
2. 华中科技大学控制科学与工程系,湖北,武汉430074 |
| |
| 基金项目： | 国家自然科学基金 (699710 18)，陕西省自然科学基金 (2 0 0 1X0 5 )资助课题 |
| |
| 摘 要： | 首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。
|
| 关 键 词： | DNA计算 NP-完全问题 有向哈密尔顿最短路 |
| 文章编号： | 1001-506X(2002)08-0102-04 |
| 修稿时间： | 2001年6月20日 |
DNA Algorithm to the Directed Shortest Hamilton Path Problem |
| |
| GAO Lin\,MA Rui nian\,XU Jin\.DNA Algorithm to the Directed Shortest Hamilton Path Problem[J].System Engineering and Electronics,2002,24(8):102-105. |
| |
| Authors: | GAO Lin\ MA Rui nian\ XU Jin\ |
| |
| Institution: | GAO Lin\+1,MA Rui nian\+1,XU Jin\+2 |
| |
| Abstract: | 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. |
| |
| Keywords: | DNA computing NP complete problem Directed shortest Hamilton path |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
