| 最小生成树DNA算法 |
| |
| 引用本文： | 周康,李刚,谢振林,徐伟.最小生成树DNA算法[J].华中科技大学学报(自然科学版),2012,40(1):30-34. |
| |
| 作者姓名： | 周康 李刚 谢振林 徐伟 |
| |
| 作者单位： | 武汉工业学院数学与计算机学院,湖北武汉,430023 |
| |
| 基金项目： | 国家自然科学基金资助项目，湖北省自然科学基金资助项目，湖北省教育科学"十一五"规划资助项目，湖北省教育厅科学技术研究(重点)项目，湖北省建设厅建设科技计划资助项目 |
| |
| 摘 要： | 为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.
|
| 关 键 词： | 粘贴模型 DNA算法 最小生成树问题 分离实验 割集 |
DNA algorithm of minimal spanning tree problem |
| |
| Zhou Kang Li Gang Xie Zhenlin Xu Wei.DNA algorithm of minimal spanning tree problem[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2012,40(1):30-34. |
| |
| Authors: | Zhou Kang Li Gang Xie Zhenlin Xu Wei |
| |
| Institution: | Zhou Kang Li Gang Xie Zhenlin Xu Wei(School of Mathematics and Computer,Wuhan Polytechnic University,Wuhan 430023,China) |
| |
| Abstract: | Sticker model was improved,calculation methods of cut set using biochemistry experiment was found,and DNA(deoxyribonucleic acid) algorithm of minimal spanning tree problem based on the methods was put forward.Separation experiment was first extended,which contained separation experiment based on separation board and separation experiment based on electrophoresis technique.The DNA algorithm of minimal spanning tree problem first breaks calculation model of DNA computing—to form minimal spanning tree gradually by means of solving minimal edge of cut set.The methods solving cut set reduces time complexity of algorithm by means of high parallelism of separation experiment,so time complexity of DNA algorithm of minimal spanning tree problem is linear. |
| |
| Keywords: | sticker model DNA （deoxyribonucleic acid） algorithm minimal spanning tree problem separation experiment cut set |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
