DNA计算在图论中的应用

摘　要：DNA计算是计算机科学和分子生物学互相结合、互相渗透而产生的新兴交叉研究领域。DNA计算具有高度的并行性、运算速度快、信息贮存容量大等优点。这为解决图论中的一些问题尤其是图论中的NP-完全问题提供了新的途径。首先介绍了DNA计算的基本原理。然后详细介绍了图最小生成树的DNA算法以及哈密顿图的DNA算法。最后介绍了DNA计算在图论应用的领域中存在的一些尚待解决的问题。

关键词：DNA计算、图论、最小生成树、哈密顿图

1. 引言
　　自从Adleman博士于1994年开创性地用DNA计算实现了7个顶点的有向图的哈密尔顿问题以来，国际上DNA计算在图论应用的研究领域中，主要集中在对哈密顿图问题、图着色问题和图顶点的最小覆盖问题的求解上。继Adleman之后1998年，Roweis给出一种基于Sticker模型的解决集合最小覆盖问题的方法。2000年，Head等又用基于质粒的DNA计算求解了图的最大团问题。同年，Faulhammer等人对骑士周游问题用DNA计算进行了求解^{( w_ij 为边e_ij的权，D=max{ w_ij })的寡聚核苷酸片断；下面通过例子解释编码问题。}