DNA计算是计算机科学和分子生物学相结合而发展起来的新型研究领域。它以DNA为计算工具，利用DNA反应的强大并行计算能力，成功地解决了诸如哈密尔顿路径、最大Clique等NP难题。本文通过对两例DNA计算的具体剖析，分析了其中的算法、运算能力、误差、以及由此引起的种种讨论，较为全面地介绍了DNA计算的概况。

DNA可能是完成计算的最完美材料。DNA计算的创始人是美国南加州大学的莱昂那多·阿德莱曼教授，他于1994年利用DNA计算方法解决了一个著名的数学难题“七顶点哈密尔顿路径”。最近，科学家们开始利用DNA计算来创造生物计算机，放在人体或生物体工作，其计算结果可通过荧光蛋白的活动来读取。DNA计算是利用DNA双螺旋结构和碱基互补配对规律进行信息编码，将要运算的对象映射成DNA分子链，通过生物酶的作用，生成各种数据池，再按照一定的规则将原始问题的数据运算高度并行地映射成DNA 分子链的可控的生化反应过程。最后，利用分子生物技术（如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等），检测所需要的运算结果。

从数学上讲，单链DNA可看作由符号A、C、G、T组成的串，同电子计算机中编码0和1一样，可表示成4 字母的集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作。不同的酶用于不同的算子，如限制内核酸酶可作为分离算子，DNA结合酶可作为绑结算子，DNA聚合酶可作为复

制算子，外核酸酶可作为删除算子等。这样，通过对DNA双螺旋进行丰富的、精确可控的化学反应以完成各种不同的运算过程，就可研制成一种以DNA为芯片的新型计算机。已被证明DNA计算至少在理论上是通用的，可以解决图灵机所能解决的所有问题。

本质上，DNA计算可以分为3类：分子内、分子间和超分子DNA计算。Takahashi致力于分子内DNA计算，借助于分子内的形态转移操作，用单DNA分子构建可编程的状态机。分子间DNA计算集中在不同DNA分子间的杂交反应，使其作为计算中的一个基本步骤，像Adleman的实验。而超分子DNA计算是利用不同序列的原始DNA分子的自装配过程进行的计算。目前，超分子DNA计算的创新及应用进入了一个新的台阶。

DNA计算机的研制无疑要经历3个阶段：首先是试管阶段，验证DNA计算原理的可行性；其次是表面阶段，这也是一个过渡性阶段，要克服试管中DNA分子的易丢失和操作难的缺点；最后是芯片阶段，只有芯片化后，DNA计算机才能走向实用。这3个阶段也就是DNA计算的3种实现方式。

经过10多年的发展已有多种DNA计算模型被提出，如剪接模型、粘贴模型、等同检测模型、插入/删除系统、最小计算模型等，这些模型都被证明和图灵机是等价的，也就是具有计算完备性。

目前，DNA计算的大量研究还停留在纸面上，很多设想和方案都是理想化的，还没有条件付诸实验，如何实现DNA计算并制造DNA计算机，还存在许多技术障碍。对于DNA计算构造的现实性及计算潜力、DNA计算中错误的减少、有效的通用算法以及人机交互等问题都需要进行进一步的研究。尤其是DNA计算中存在的误码，这种误码是依概率随机产生的，并能被逐级放大。误码率直接影响DNA的计算精度，目前还不能有效克服这一问题。也许DNA计算机仅起一个运算器的作用，即便如此，这种DNA计算与传统计算机互补所获得的计算机也将产生不可估量的影响。