最小生成树DNA算法  

DNA algorithm of minimal spanning tree problem

作　　者：周康[1] 李刚[1] 谢振林[1] 徐伟[1] 

机构地区：[1]武汉工业学院数学与计算机学院,湖北武汉430023

出　　处：《华中科技大学学报（自然科学版）》2012年第1期30-34,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61179032);湖北省自然科学基金资助项目(2011CDB229);湖北省教育科学'十一五'规划资助项目(2010B290;2009B217);湖北省教育厅科学技术研究(重点)项目(D20111702);湖北省建设厅建设科技计划资助项目(2011-29)

摘　　要：为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.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 ex- periment, so time complexity of DNA algorithm of minimal spanning tree problem is linear.

关 键 词：粘贴模型 DNA算法 最小生成树问题 分离实验 割集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]