DNA计算是一种模拟生物分子DNA的结构并借助分子生物技术进行计算的新方法,DNA计算主要分为两步:第一步是生成问题的所有可能解,第二步是解的检测。它作为一门新兴的交叉学科正逐渐发展起来,在解决大规模并行计算问题上,特别是在解决NP一完全问题上有其不可估量的优势。1994年,Adleman利用DNA计算解决了图论中的哈密顿路径问题,并成功地进行了实验。其目标是产生以DNA计算模型为背景、具有海量的存储遗传密码以及极快运行速度的新一代计算机。DNA计算的基本思想是:利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池(data pool),然后按照特定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等,检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成可以控制的生物化学反应,并以此来完成运算,使得从反应后的产物中能得到全部的解空间。在DNA计算系统中,DNA分子中的密码作为存储的数据,当DNA分子间在某种酶的作用下瞬间完成某种生物化学反应时,可以从一种基因代码变为另一种基因代码。DNA计算实际也就是通过对DNA双螺旋进行丰富的精确可控的化学反应,包括标记、扩增或者破坏原有链来完成各种不同的运算过程。本文从DNA计算所使用的DNA分子结构角度,对目前DNA编码问题及其在解决NP-完全问题方面的应用进行了介绍。对于TSP问题,利用DNA序列表示权值大小、熔点温度控制编码、粘帖系统等三种方式实现算法;提出了一种基于可满足解空间的最小顶点覆盖问题的DNA计算模型;在对骑士问题处理中利用粘贴模型,它是应用DNA链作为信息表示的物理基础,它的计算是基于Watson-Crick的补码变化规律。