方　铖

摘要：综述了DNA计算原理和特点，接着介绍了DNA计算的研究现状，指出了目前DNA计算的主要研究方向和DNA计算需要解决问题，最后对DNA计算的发展前景进行了展望。

关键词：DNA计算NP完全问题图论

中图分类号TP301.6文献标识码A文章编号：1002-2422(2007)05-0002-02

对于一类被称之为NP完全问题的复杂计算，计算机的处理时间会随着问题规模的增大呈现指数级增长，因此迫切需要一种新的计算形式来解决它，DNA计算就是一种新的尝试。

1DNA计算原理、特点

1.1DNA计算原理

DNA计算是伴随着分子生物学的兴起而出现的。生物学家研究发现，DNA有一种特性，能够携带生物体内各种细胞拥有的大量基因物质。计算机专家从中得到启迪，正在研制液体DNA电脑。这种DNA电脑的工作原理是以瞬间发生的生化反应为基础，通过和酶的相互作用，将反应过程进行分子编码，对问题以新的DNA编码形式加以解答。

DNA是一种由许多脱氧核苷酸的单体连接在一起形成的聚合物。核苷酸是由三部分组成的：脱氧核糖、磷酸和含氮碱基，其中碱基有四种类型：腺嘌呤A、鸟嘌呤G、胸腺嘧啶T、胞嘧啶C，与之对应的核苷酸也有四种，分别称为脱氧腺苷酸(A)、脱氧鸟苷酸(G)、脱氧胸苷酸(T)、脱氧胞苷酸(C)。单核苷酸端对端连接在一起形成DNA链，在这种连接过程中，碱基严格遵循下述配对原则：A、T配对，G、C配对。

一个DNA单链可看作由四个不同符号A、T、G和C连成的串，就像电子计算机中的O、1编码一样，可使用四个字母的集合∑={A，G，C，T}，并按照DNA双螺旋结构和碱基互补配对原则对问题进行编码，酶可看作模拟在DNA序列上的计算，不同的酶相当于作用在DNA串上的不同的算子，主要的酶操作有：限制内切酶进行切割操作、接合酶作连接操作、聚合酶可用作复制、外核酸酶可用作删除等等。

DNA算法解决计算问题的基本思想是：把要运算的对象映射成DNA分子链，在DNA溶液的试管里，在生物酶的作用下，生成各种数据池，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程，最后。利用分子生物技术如聚合酶链反应、聚合重叠放大技术、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，破获运算结果。

完整的DNA计算过程包括数据输入、运算以及结果的输出。首先，将问题空间的对象映射成DNA分子链；第二步，利用DNA分子链的高度并行运算的特点，用可控的生化操作完成正确答案的筛选工作；第三步，结果的输出，主要通过测定来判断是否有解，如果有解则将DNA链进行译码，就得到所求问题的解。

1.2DNA计算优点、不足

1.2.1DNA计算具有以下优点：

(1)运算速度快：目前最快的电子计算机的计算速度为10¹²次/秒，而对于DNA计算机，如果是两个DNA的连接视为一次操作，又假定4*10¹⁴个边DNA片断有一半发生了连接反应，则DNA计算机的运算速度为10¹⁴次/秒。

(2)低能耗：生化反应所需要的能量消耗很小，完成同样的运算DNA计算所消耗的能量是大型机的十亿分之一。

(3)存储容量高：DNA存储信息的密度是1bit／nm³，而当前录像带的信息存储密度仅为1bit/12¹²nm³。

(4)可真正实现并行工作：传统电子计算机主要是串行工作，而DNA计算机可视为多CPU的并行工作，可以实现现有计算机无法真正实现的模糊推理和神经网络运算功能。对于DNA计算机，一个DNA分子相当于一个CPU，在