摘要
为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树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.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2012年第1期30-34,共5页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(61179032)
湖北省自然科学基金资助项目(2011CDB229)
湖北省教育科学'十一五'规划资助项目(2010B290
2009B217)
湖北省教育厅科学技术研究(重点)项目(D20111702)
湖北省建设厅建设科技计划资助项目(2011-29)
关键词
粘贴模型
DNA算法
最小生成树问题
分离实验
割集
sticker model
DNA （deoxyribonucleic acid） algorithm
minimal spanning tree problem
separation experiment
cut set
