理论：DNA计算

www.quantumac.com

严 明 达
(中国科学院上海生物化学研究所，上海200031)

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

关键词 DNA计算， NP难题， 哈密尔顿路径问题， 最大Clique问题


引 言

  分子水平上进行计算的概念最早是在六十年代早期由Richard Feynman提出的
[1]。但是由于当时尚缺乏合适的材料、工具与方法，Feynman的“超微型计算机”
想法只能是一种超前的、美好的愿望。而与此同时在生物学领域，分子生物学正逐
渐出现并成熟，使生物学的研究深入到了分子水平。尤其是到了八十年代，随着
PCR等现代生物技术的日益完善，分子计算的时机事实上已基本成熟，只是人们一
度淡忘了它。直到1994年，Leonard Adleman发表了如何用基本分子生物学手段解
决哈密尔顿路径的计算难题[2]，人们才猛然意识到，分子计算的时代已经到来，
一直被认为是遗传信息载体的DNA其实也可以用来作为计算工具，即所谓的DNA计算
机[3]。短短几年来，DNA计算领域的研究成果层出不穷，大大促进了数学、计算机
学和生物学的交流与合作[4]。

哈密尔顿路径问题与Adleman实验

    所谓哈密尔顿路径问题是指：在由n个顶点与有向线段组成的图形中，问能
否找到一条途径，从顶点Vin出发、到Vout结束，途中经历每个顶点一次且只有一
次[5]。这样的途径就称为哈密尔顿途径。目前为止虽然已有很多算法寻找哈密尔
顿路径，但都面临“指数爆炸”、或者叫作“组合灾难”的复杂性问题，没有有效
的（所谓“多项式时间”）算法来解决。

  Adleman提出了一个由7个顶点和14条有向线段组成的简单图形,并设Vin=0、
Vout=6,那么容易看出，图中存在一条哈密尔顿途径：0→1→2→3→4→5→6。若有
向线段2-3不存在，则没有哈密尔顿途径；若Vin=3、Vout=5，则也找不到哈密尔顿
途径。

  Adleman设计了如下算法：
  第一步，组建图中所有可能存在的路径的集合；
  第二步，筛选出以Vin为开头、Vout为结尾的途径；
  第三步，筛选出共经历n个顶点的路径；
  第四步，筛选经历了每一个顶点的路径；
  第五步，经过上述三次筛选，考察有否路径存在，即回答了哈密尔顿路径问题
。

  应用DNA为材料、分子生物学方法为手段，Adleman成功地完成了各步：

  首先，设计并合成若干个20mer长的寡聚核苷酸，以对应每一个顶点和有向线
段。代表顶点i的寡聚核苷酸记为Oi；代表有向线段i→j的则记为Oi→j，其前
10mer为Oi的后10mer,其后10mer为Oj的前10mer。另外，顶点Oi的互补链记为`Oi。
现将`Oi、Oi→j共21种寡聚核苷酸混合、连接。容易想象，在`Oi的指导下，各条
Oi→j相互连接，构成了所有可能路径的总集。即完成了算法的第一步。

  接着，应用PCR技术，以第一步连接产物为模板，O0、`O6为引物进行扩增，所
得产物即为算法第二步的结果。将PCR产物走Agarose凝胶电泳，可以将相差20mer
的各个条带分离开，其中140bp条带显然就是经历了7个顶点的路径集，切胶回收它
即完成了算法第三步。然后应用亲和纯化法，用磁珠标记的`O1与回收产物（经变
性为单链）结合，纯化得到含O1的子集，再依次用`O2、`O3、`O4、`O5亲和纯化，
就完成了算法第四步的筛选。

  再次PCR检测即为算法的第五步。事实上，Adleman用O0、`Oi（i=1-6）引物对
进行了一系列6个PCR，不仅回答了存在哈密尔顿路径，而且可以明确指出这条哈密
尔顿路径的组成。即由系列PCR产物大小40、60、80、100、120、140bp，推断出该
途径为0→1→2→3→4→5→6。

  Adleman实验成功解决了哈密尔顿路径问题，可谓是开创了DNA计算的先河。从
此，“DNA计算”、“DNA计算机”的大名迅速出现在各种媒体上，类似的研究也竞
相报道。下面介绍的最大Clique问题就是其中的一例。

最大Clique问题及其DNA计算解决

  数学上Clique是指每两个顶点之间均有线段相连的一系列顶点所组成的图形。
故所谓“最大Clique问题”就是：在一个N个顶点、M条线段组成的网络图中，问最
大的Clique具有几个顶点。与哈密尔顿路径问题相类似，最大Clique问题同样是具
有“指数爆炸”特征的计算难题。

  如何应用DNA计算机来解答这个问题呢？Ouyang[6]在文中举了个例子，是一个
6顶点、11条线段的简单网络。容易看出，顶点（2，3，4，5）组成了最大Clique
，所以这个图的最大Clique问题之解为4。

  Ouyang采用的算法为以下三步：

  第一步，设计一个6位的二进制数来描述Clique，该数第n位为1则表示顶点n位
于此Clique中，反之为0则表示不是此Clique中的顶点。如Clique（4，1，0）可描
述为2进制数010011，Clique（5，4，3，2）为111100。可见，6位二进制数的集合
就是6顶点网络中所有可能的Clique的总集。

  第二步，画出“互补图”，即各顶点由原图中所没有的线段相连构成的图。在
第一步总集中有这些线段的二进制数显然不是真正的Clique，应予以排除。由互补
图易知这些数为：xxx1x1,1xxxx1,1xxx1x,xx1x1x（x=0或1）。剩余的数即为原图
中真正Clique的集合。

  第三步，排列第二步所得集合，含最多1的二进制数就是最大Clique，其1的个
数即为最大Clique问题的答案。

  Ouyang通过精心设计，合成了12条寡聚核苷酸，分别编码第1到第6位的“0”
和“1”。每一条由三部分组成：两头的Pi,Pi+1部分分别为20mer的位置符，中间
的Vi则为数值符（10mer表示“0”，0mer表示“1”）。混合在一起，通过PCR循环
，互补链部分退火结合、并在Taq酶作用下延伸，若干循环后即得到代表二进制数到111111的所有DNA片断。为去除不足6位的延伸，用P0、`P6为引物进行扩
增，便完成了算法第一步。

  根据寡聚核苷酸的设计，若i位数值为1，Vi是0bp,Pi与Pi+1相邻，正好构成一
个内切酶识别位点；若i位数值为0，由于Vi 10bp的插入，破坏了该酶切位点。因
此，第二步的去除就可以由内切酶反应来完成了。比如要去除xxx1x1，就先用一种
内切酶切断xxxxx1，再用另一种内切酶切断xxx1xx，合并两种酶切产物，即为无
xxx1x1的集合了。其他三种如法炮制、依次去除。最终再以P0、`P6为引物进行
PCR扩增，所得产物就是第二步的结果了。

  最后，简单的电泳分离即可完成第三步：最短的DNA片断所含1最多，代表了最
大Clique。实验结果所得到最短的片断是160bp,扣除140bp的位置符长度，数值符
总长度为20bp，表明含有2个“0”、4个“1”。故这个最大Clique问题的答案即为
4。
事实上，进一步利于克隆技术，将该160bp条带克隆、并测序，就可以回答这个最
大Clique由哪几个顶点所构成。测序结果表明此DNA片断代表二进制数111100，正
是Clique（5，4，3，2）。

DNA计算的算法

  在计算机学中，问题的困难程度是由解题所需的计算时间（机时）所决定的。
机时是问题大小的函数。若这个函数为多项式函数，则问题可称为“多项式时间（
Polynomial time）”问题；若不是，则称为“非多项式时间”问题，往往被视作
不可解问题[7]。因为举例来说，设解答大小为10的问题需1μs机时，如果是一个
机时函数为O(n2) 的“多项式时间”问题，当问题扩大为100时，解决需100μs；
而如果是一个机时函数为O(2n)的“指数时间”问题，问题扩大为100后，解题需
3.9×1011世纪！

  在“非多项式时间”问题中，有一部分为NP（non-deterministic polymial
time）问题，是指它的答案可以在多项式时间内得以验证。换而言之，若存在一个
先知，告诉了我们问题的答案，我们就可以在多项式时间内验证它。NP问题中最重
要的子集是“NP-完全问题”，任何NP问题均可以经多项式时间运算后转化为NP-完
全问题。目前计算机学中许多重大的问题几乎都是NP-完全问题，为了解答它们，
大小得有所限制，还不得不采用一定的近似，用牺牲精度来换取机时。

  上面提到的哈密尔顿路径问题、最大Clique问题，即属于著名的NP-完全问题
。其它作者也提出了不同NP-完全问题的DNA解决法[8,9]。事实上，Lipton提出的
模型指出[10]，原则上DNA计算机可用于解决任何NP问题，而非仅仅原始文献中那
些简单的示意问题。所有这些问题的一个特征是：存在与问题大小呈指数关系的“
可能解”，每一个解均可以在多项式时间内加以验证。DNA计算机正是运用了这一
特征，利用DNA编码所有的“可能解”，而后进行种种筛选，最终找到答案。

  DNA计算机的这种算法，从某种角度看，得益于有“先知”提供了问题的答案
。这个“先知”不是别人，正是DNA连接反应中强大无比的运算能力。
强大的运算能力

  普通台式计算机能以每秒106次运算的高速运行，而目前最快的超级计算机可
达到约1012/秒的运算速度。那么在试管中慢吞吞进行的DNA分子反应又是靠什么来
赶超它们的呢？

  以两段DNA片断的连接视作一次运算，在Adleman实验的第一步有50pmol`Oi、
50pmol Oi→j参与的连接体系中，约有1014次连接运算；若用μmol级的DNA用量，
就可以达到1020次，甚至更多。而如此多的运算在一次连接反应中完成，所需时间
为数小时，即104－5秒。因此，每秒进行的运算就可以远远超过超级计算机。可见
，并行运算是DNA计算机制胜的法宝。虽然现有的超级计算机也具有并行运算能力
，但仅仅能够进行数千次级的并行运算，而在DNA计算机中，可以轻易地达到数十
亿次级的并行运算。

  同时，DNA计算是低能耗的运算。连接反应需水解一个ATP提供能量，所释
Gibbs自由能为8kcal/mol[11]。由此计算，1J能量足以提供DNA计算机作2×1019次
运算，而这些能量提供给现有的超级计算机却仅能作109次运算。

  此外，信息存储高密度也是DNA计算机的强大之处。于DNA中存储信息，1bit信
息所需空间仅仅是nm3级的（DNA碱基对的空间大小）, 1μmol DNA就足以编码2Gb
的信息。而现有的磁记录设备，如磁盘、磁带，存储1bit约需1012nm3。果蝇170,
000,000bp基因组一级结构信息存在于果蝇的每一套染色体中，但若存储于磁盘上
，需要40张3’软盘！

关于计算中的误差

  DNA计算机会不会出错呢？考察整个DNA计算的操作过程，亲和纯化是最易出错
的步骤。Adleman实验中共需进行五步亲和纯化，还不算多，但可以想象，由于低
信噪比所引入的误差会使更复杂的运算操作最终无法成功。尽管可以作些改进
[12,13]，但最好还应减少乃至不用这一类方法。Ouyang最大Clique问题的解决就
成功应用了内切酶反应，从而避免了亲和层析。

  另外，就模板指导的寡聚核苷酸连接反应的保真度问题，James等做了专门研
究后指出[14]，由于寡聚核苷酸二级结构的影响，以及连接酶允许少量的A:G配对
，确会有1/2824的出错率。虽然与Intel曾经风波一场的Pentium芯片浮点运算出错
相比，还略胜一筹，但的确是十分严重的出错率了。正常的Intel芯片一般才
1/109的出错。由此作者提出了几点建议：提高连接温度，缩短连接时间，寡聚核
苷酸长度也应缩短，以及生物工程改造以生产高保真的连接酶等等。

  此外，操作中如何减少DNA链的丢失也是减小误差的一个方面。Liu, Q.等摒弃
了让DNA链悬浮在溶液中传统做法，另辟捷径，将DNA固定在玻片表面进行操作
[15,16]。事实上，金、硅片也是很好的载体。Guo, Z.等对其中表面化学作了详尽
的研究[17]。此类方法使用适当的核酸外切酶对固定化了的DNA作选择性切割，以
达到筛选的目的。DNA链的损失由此可以降到最低程度。但同时出现的问题是，随
着问题规模的增大，能否提供足够的二维表面来作运算呢？

一点质疑

  DNA计算机的概念问世后不久，就有研究人员指出[18]，在类似于哈密尔顿路
径问题的NP难题中，真正难解的是图中路径既不多也不少的那些，即所谓的“
middle-ground”：n个顶点，有约n(log n)条路径。若路径很少或很多，已有十分
有效的算法可以解决[19]。由此估算：在Adlemann实验中的第一步，构建经n个顶
点的所有路径集合可用（log n）n表示，该集合所需的DNA为20n(log n)nbp。若n
增加为23，就需要kg级的DNA来构建第一步的总集合；若n为70，则这个量猛增到
1025kg之多，简直无法想象！

  而现实世界中遇到的哈密尔顿路径问题往往具有成百上千的顶点，通过现有的
算法与计算机，可以方便地得到哈密尔顿路径的近似解。但用DNA计算机，哪怕将
编码每个顶点的寡聚核苷酸长度减少为1（事实上是不可能的，1b只能代表4个顶点
），也至少需要102－3bp来代表一条路径，那么一个穷极库就要4EXP(102-3)b之多
，即1070。这是一个无比巨大的数，已接近我们的宇宙中所有原子的总个数！

  换言之，当NP问题规模逐渐增大时，电子计算机面临的是所耗机时的指数爆炸
，而DNA计算机面临的则是“可能解”库大小的指数爆炸。

  但是应当看到，今天电子计算机之高速高效是近半个世纪以来飞速发展的结果
，而分子计算机才刚刚诞生。随着计算机学带来算法上的进步和分子生物学带来操
作上的革新，我们有理由相信DNA计算的光明前途。

DNA计算与生物进化

  仔细考察Adleman实验，在连接反应中加入的`Oi可视作一种“强制指导者”。
因为从理论上讲，没有`Oi，Oi→j的随机连接照样可以创造出最终的哈密尔顿路径
来。但有了这种“强制指导者”，使得答案出现的机率大大提高了。那么，在生物
演化过程中，遗传物质的随机组合是否也有某种强制指导者存在呢？由于它使得变
异朝最可能成功的方向进行。若能找到这个强制因素，定是一个非同寻常的认识自
然的成就。

  Stemmer则从另一个角度指出[20]，不一定非要构建一个包含所有可能性的总
集合才进行DNA的搜索运算。自然进化也可以看作是在遗传库中筛选的结果，而这
个遗传库其实并不大（如地球上人类共有5×109个个体）。但筛选这个中等规模的
库仍然可以产生十分复杂的DNA序列，关键就是得益于多次、反复、递归的选择过
程。这意味着最佳答案可以在一个库经扩增、变异成为第二个库的过程中反复地选
择。它胜过了任何在单一库中的筛选。

  举例来说，人类基因组大约编码100,000个蛋白质，即使只有300个氨基酸组成
的小蛋白，它们可能的基因也有20300（即10390）之众，若是从一个完整的库中一
次筛选得到，这个库该有多么大呢？！所以说不可能有如此巨大的基因库可以使一
步到位的筛选成功。同样，要在5个位点得到5个特定的8bp内切酶位点，照“一步
筛选法”，就需（48）5＝1024之库规模，也是不可能的。但是若分步筛选，每一
步在48大小的库中筛选一位点，五步完成却是十分实际可行的。

  自然变异可以是性别、同源重组、以及点突变等进程，而体外进化的研究中，
重组可以通过所谓“有性PCR [21]”进行。这也为DNA计算机的发展提供了一条有
用的线索。

DNA计算的前景

  DNA计算机的出现引起了世界上诸多科学家的关注。1995年4月，近两百位计算
机学家、分子生物学家聚集在Princeton大学对DNA计算进行了热烈讨论，憧憬其发
展前景，大大开拓了它可能的应用领域。

  Lipton和他的两个学生Boneh和Dunworth称已发展了一种方法来解DES密码
[22,23]。所谓DES(data encryption standard system)，是由美国国家安全局研
制开发的一套加密系统，为政府及众多公司所采用。它使用256种密钥进行加密，
若在现有计算机上将如此多的密钥一一尝试来解码，得化费几乎无限多的机时。然
而应用DNA计算，Lipton他们用DNA链来构建所有可能的密钥，然后并行尝试。据称
经若干月的分子生物学操作，最终可以拿到对应DES正确密钥的唯一一条DNA。

  除了可以解决NP类的问题，DNA计算机能否发展成可解决一切计算问题的普遍
性计算机呢？答案是肯定的。事实上，Guarnieri等已成功地解决了两个二进制非
负整数的相加[24]。要设计DNA普遍性计算机，这正是所要求的最基本的运算步骤
。作者通过巧妙的编码，使得两数对应位的相加变为结果链在所投入的加数的几种
寡聚核苷酸中的杂交选择、而后延伸的分子生物学反应，经PCR循环（实为单向
PCR）富集结果链，作下一步的相加运算。作者称之为“水平链式反应”，意为每
一步反应为结果链在投入寡聚核苷酸为模板指导下的延伸。最终结果可通过适当的
杂交、或PCR、或直接的DNA测序读得。

  此外，Adleman领导的研究小组提出了一种“胶水模型 [25]”，可以重复使用
DNA，完成读、写的记忆操作。但目前，由于实际操作上的困难，该模型还只具有
理论研究意义。

  另一类富有前景的计算模型是利用DNA的自装配行为。很早人们就已发现DNA除
了双螺旋结构外，还存在着许多异常结构[26,27,28]，如节点[29]、Holliday交叉
[30]、octahedra[31]等。人们发展了“序列对称最小法[32]”技术来研究DNA一级
结构与形成其异常高级结构的关系，可以设计合成各组分，使它们在溶液中杂交形
成所需的特殊结构。Winfree等由此考虑可利用这一自装配特性作为计算工具[33]
，指出复杂分枝结构“双交叉[34]”通过自装配形成二维片状或三维球状过程是强
大的计算模型。至少自装配成二维片状模型是确实可行的。

结 语

  DNA计算的未来必定在两方面上有所突破：算法上，需要解决的是如何避免
DNA用量的指数扩增，以便充分发挥DNA并行运算的优势，真正解决大规模的计算难
题；实验操作上，随着生物学自动化设备如bio-robot[35,36]、
biochip[37]/microarray[38]等系统的研制开发，必将有助于DNA计算机摆脱目前
生物技术如凝胶电泳、亲和层析、分子克隆等慢速、低信噪比的束缚，向高速化和
精确化迈进。

  尤其重要的是，DNA计算大大开拓了我们对计算的认识，使人们重新思考什么
是计算机。在这以前，人们从没有想到过普通的DNA连接反应里居然蕴藏着如此巨
大的计算能力。那么在细胞中进行的其他酶促反应是否也如此呢？转录、翻译调控
对细胞生命行为起着巨大的作用，在它们的背后是否存在着某种计算机制呢？这些
机制又能否应用到科学计算中去呢？都将有待于分子生物学与计算机学的进一步发
展与合作。