Biology 版 (精华区)

发信人: cameran (竹晨), 信区: Biology
标  题: DNA计算（上）
发信站: 哈工大紫丁香 (2001年05月16日18:45:09 星期三), 站内信件

----------------------------------------------------------------------------
----
严 明 达
(中国科学院上海生物化学研究所，上海200031)
摘 要 DNA计算是计算机科学和分子生物学相结合而发展起来的新型研究领域。它以DNA
为计算工具，利用DNA反应的强大并行计算能力，成功地解决了诸如哈密尔顿路径、最大
Clique等NP难题。本文通过对两例DNA计算的具体剖析，分析了其中的算法、运算能力、
误差、以及由此引起的种种讨论，较为全面地介绍了DNA计算的概况。
关键词 DNA计算， NP难题， 哈密尔顿路径问题， 最大Clique问题
引 言
    分子水平上进行计算的概念最早是在六十年代早期由Richard Feynman提出的[1]。
但是由于当时尚缺乏合适的材料、工具与方法，Feynman的“超微型计算机”想法只能是
一种超前的、美好的愿望。而与此同时在生物学领域，分子生物学正逐渐出现并成熟，
使生物学的研究深入到了分子水平。尤其是到了八十年代，随着PCR等现代生物技术的日
益完善，分子计算的时机事实上已基本成熟，只是人们一度淡忘了它。直到1994年，Le
onard 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的后1
0mer,其后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条线段组成的网络图中，问最大的Cliq
ue具有几个顶点。与哈密尔顿路径问题相类似，最大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酶作用下延伸，若干循环后即得到代表二进制数000000到111111的所有
DNA片断。为去除不足6位的延伸，用P0、`P6为引物进行扩增，便完成了算法第一步。
    根据寡聚核苷酸的设计，若i位数值为1，Vi是0bp,Pi与Pi+1相邻，正好构成一个内
切酶识别位点；若i位数值为0，由于Vi 10bp的插入，破坏了该酶切位点。因此，第二步
的去除就可以由内切酶反应来完成了。比如要去除xxx1x1，就先用一种内切酶切断xxxx
x1，再用另一种内切酶切断xxx1xx，合并两种酶切产物，即为无xxx1x1的集合了。其他
三种如法炮制、依次去除。最终再以P0、`P6为引物进行PCR扩增，所得产物就是第二步
的结果了。
    最后，简单的电泳分离即可完成第三步：最短的DNA片断所含1最多，代表了最大Cl
ique。实验结果所得到最短的片断是160bp,扣除140bp的位置符长度，数值符总长度为2
0bp，表明含有2个“0”、4个“1”。故这个最大Clique问题的答案即为4。
事实上，进一步利于克隆技术，将该160bp条带克隆、并测序，就可以回答这个最大Cli
que由哪几个顶点所构成。测序结果表明此DNA片断代表二进制数111100，正是Clique（
5，4，3，2）。
DNA计算的算法
    在计算机学中，问题的困难程度是由解题所需的计算时间（机时）所决定的。机时
是问题大小的函数。若这个函数为多项式函数，则问题可称为“多项式时间（Polynomi
al 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连接反应中强大无比的运算能力。

--
欲讯秋情众莫知, 喃喃负手叩东篱。
孤标傲世偕谁隐，一样花开为底迟？
圃露庭霜何寂寞，鸿归蛩病可相思？
休言举世无谈者，解语何妨片语时。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.175]