摘 要：DNA计算是计算机科学和分子生物学互相结合、互相渗透而产生的新兴交叉研究领域。DNA计算具有高度的并行性、运算速度快、信息贮存容量大等优点。这为解决图论中的一些问题尤其是图论中的NP-完全问题提供了新的途径。首先介绍了DNA计算的基本原理。然后详细介绍了图最小生成树的DNA算法以及哈密顿图的DNA算法。最后介绍了DNA计算在图论应用的领域中存在的一些尚待解决的问题。
关键词：DNA计算、图论、最小生成树、哈密顿图
1. 引言 自从Adleman博士于1994年开创性地用DNA计算实现了7个顶点的有向图的哈密尔顿问题以来，国际上DNA计算在图论应用的研究领域中，主要集中在对哈密顿图问题、图着色问题和图顶点的最小覆盖问题的求解上。继Adleman之后1998年，Roweis给出一种基于Sticker模型的解决集合最小覆盖问题的方法。2000年，Head等又用基于质粒的DNA计算求解了图的最大团问题。同年，Faulhammer等人对骑士周游问题用DNA计算进行了求解( wij 为边eij的权，D=max{ wij })的寡聚核苷酸片断；下面通过例子解释编码问题。
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。
