随着越来越多复杂问题的出现,电子计算机已经很难满足人们的需要。因为DNA计算具有存贮容量大、并行性强等优点。现阶段被科学家们广泛用来解决各类疑难问题。它的主要思想是以生物分子结构为基础,并结合一些生物操作来解决相关问题。DNA计算首次把数学问题与生物学有机地结合起来,这也是一崭新的领域,具有一定的研究意义。且近些年来,被科学家们广泛用来解决图论中的一些NP-完全问题,如最大独立集问题、最大团问题、最大匹配问题及最小顶点覆盖问题等。文章首先给出了DNA分子的基本理论知识,如DNA分子的结构、DNA分子的基本操作,且详细介绍了编码过程中容易出现的问题、影响编码的因素、并给出了几种常用的编码方法,在该文中还介绍了基于生物操作的DNA计算模型：试管、表面和芯片模型；基于分子结构特性的DNA计算模型：剪接、粘贴、质粒、发夹、自组装和分子信标模型。图论与组合中存在一些重要的NP-完全问题。本文主要讨论了图的最小顶点覆盖问题,并详细介绍了解决图的最小顶点覆盖问题几种模型。其基本思路是把图的最小顶点覆盖问题转化为比较常见的0-1规划问题。这也是文章的关键之处。然后,在此基础上,给出了表面模型、分子信标模型和改进的芯片模型,并进行了分析和总结,具有一定的研究意义。