DNA计算是以编码携带遗传信息的DNA序列和与之有关的一些生物酶等为最基本物质,运用生物操作来实现并行信息处理的一种新型的分子水平上的生物计算方式。1994年,Adleman首先提出DNA计算的方法来解决NP-完全问题,对NP-完全问题的计算提供了一种新方法。此后学者们不断地研究利用DNA分子或者是其它生物分子来进行计算过程,并取得了令人瞩目的成果。DNA计算的主要思想是：利用DNA分子特有的双螺旋结构及碱基互补配对性质,把需要解决的问题编码并映射成相应的DNA链,通过生物酶的参与形成数据池,然后按照一系列的实验步骤把待解决问题的原始数据经过运算高度并行地映射成DNA分子链的可控制的生化过程,再利用现代分子生物技术检测所需要的运算结果。本文从DNA计算的基础理论问题出发,研究了DNA计算模型及其在解决两类困难问题上的应用。详细研究内容的安排如下：本文讨论了文中用到的质粒DNA计算模型和闭环DNA计算模型。质粒DNA计算模型是一种以闭环状质粒作为基础的DNA计算模型,在该模型中被用到的质粒具有一段特殊的DNA插入序列,全部的片断确定在对应的限制性内切位点,运用剪切及粘贴的生物操作执行计算过程。闭环DNA计算模型与质粒DNA计算模型有许多异同点,闭环DNA计算模型具有更大的研究价值和更广的应用范围。基于质粒DNA计算模型,给出了求解图的最小顶点覆盖问题的DNA算法。该算法通过合适的编码以及基本的生物操作完成解的生成及最终解的分离。基于闭环DNA计算模型和其主要的生物化学实验,介绍了求解最大加权独立集问题的闭环DNA算法。该算法首先通过适当的编码以及多次删除实验获得所有独立集,再用其它实验手段得到图的最大加权独立集。