Biology 版 (精华区)

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

----------------------------------------------------------------------------
----
强大的运算能力
    普通台式计算机能以每秒106次运算的高速运行，而目前最快的超级计算机可达到约
1012/秒的运算速度。那么在试管中慢吞吞进行的DNA分子反应又是靠什么来赶超它们的
呢？
    以两段DNA片断的连接视作一次运算，在Adleman实验的第一步有50pmol`Oi、50pmo
l Oi→j参与的连接体系中，约有1014次连接运算；若用μmol级的DNA用量，就可以达到
1020次，甚至更多。而如此多的运算在一次连接反应中完成，所需时间为数小时，即10
4－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/2
824的出错率。虽然与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个顶点的所有路径集合可用（lo
g 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内切酶位点，照“一步筛选法”，就需（4
8）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]、oc
tahedra[31]等。人们发展了“序列对称最小法[32]”技术来研究DNA一级结构与形成其
异常高级结构的关系，可以设计合成各组分，使它们在溶液中杂交形成所需的特殊结构
。Winfree等由此考虑可利用这一自装配特性作为计算工具[33]，指出复杂分枝结构“双
交叉[34]”通过自装配形成二维片状或三维球状过程是强大的计算模型。至少自装配成
二维片状模型是确实可行的。
结 语
    DNA计算的未来必定在两方面上有所突破：算法上，需要解决的是如何避免DNA用量
的指数扩增，以便充分发挥DNA并行运算的优势，真正解决大规模的计算难题；实验操作
上，随着生物学自动化设备如bio-robot[35,36]、biochip[37]/microarray[38]等系统
的研制开发，必将有助于DNA计算机摆脱目前生物技术如凝胶电泳、亲和层析、分子克隆
等慢速、低信噪比的束缚，向高速化和精确化迈进。
    尤其重要的是，DNA计算大大开拓了我们对计算的认识，使人们重新思考什么是计算
机。在这以前，人们从没有想到过普通的DNA连接反应里居然蕴藏着如此巨大的计算能力
。那么在细胞中进行的其他酶促反应是否也如此呢？转录、翻译调控对细胞生命行为起
着巨大的作用，在它们的背后是否存在着某种计算机制呢？这些机制又能否应用到科学
计算中去呢？都将有待于分子生物学与计算机学的进一步发展与合作。
参考文献
Feynman RP: There’s plenty of room at the bottom. Miniaturization. 1961:282
-296
Adleman L: Molecular computation of solutions to combinatorial problems. Sci
ence 1994, 266:1021-1024
Friedman Y: DNA Computers. http://dna2z.com/dnacpu/dna.html
Gibbons A, Amos M, Hodgson D: DNA computing. Curr. Opin. Biotech. 1997, 8:10
3-106
Garey MR, Johnson DS: Computers and Intractablility. Freeman, San Francisco,
 CA, 1979
Ouyang Q, Kaplan PD, Liu S, Libchaber A: DNA solution of the maximal clique 
problem. Science 1997, 278:446-449
Gifford DK: On the path to computation with DNA. Science 1994, 266:993-994
Amos M, Gibbons A, Hodgson D: Error-resistant implementation of DNA computat
ions. In Proceedings of the Second Annual Meeting on DNA Based Computers. DI
MACS: Series in Discrete Mathematics and Theoretical Computer Science. Provi
dence, PI: American Mathematical Society; 1996
Jonoska N, Karl SA: A molecular computation of the road coloring problem. In
 Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Se
ries in Discrete Mathematics and Theoretical Computer Science. Providence, P
I: American Mathematical Society; 1996
Lipton RJ.: DNA solution of hard computational problems. Science 1995, 268:5
42-545
Watson JD, Hpkins NH, Roberts JW, Steitz JA, Weiner AM: Molecular Biology of
 the Gene Benjamin/Cummings, Menlo Park, CA, ed.3, 1987
Karp RM, Kenyon C, Waarts O: Error-resilient DNA computation. In Proceedings
 of the 7th ACM-SIAM Symposium on Discrete Algorithms: 1996 Jan 28-30; Atlan
ta. Philadelphia: SIAM; 1996:458-467
Boneh D, Dunworth C, Lipton RJ, Sgall J: Making DNA computers error resistan
t. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMAC
S: Series in Discrete Mathematics and Theoretical Computer Science. Providen
ce, PI: American Mathematical Society; 1996
James KD, Boles AR, Henckel D, Ellington AD: The fidellity of templated-dire
cted oligonucleotide ligation an its relevance to DNA computation. Nucleic A
cids Res. 1998, 26:5203-5211
Liu Q, Guo Z, Condon AE, Corn RM, Lagally MG, Smith LM: A surface-based appr
oach to DNA computation. In Proceedings of the Second Annual Meeting on DNA 
Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Comp
uter Science. Providence, PI: American Mathematical Society; 1996
Corn RM, Smith LM, Condon AE, Lagally MG: DNA Computing and Informatics at S
urfaces. http://www.corninfo.chem.wisc.edu/writings/DNAcomputing.html
Guo Z, Guilfoyle RA, Thiel AJ, Wang R, Smith LM: Direct fluorescence analysi
s of genetic polymorphisms hybridization with oligonucleotide arrays on glas
s supports. Nucleic Acids Res 1994, 22:5456-5465
Linial M et al.: On the potential of molecular computing. Science 1995, 268:
481-483
Papadimitriou CH, Steiglitz K: Combinatorial Optimization: Algorithms and Co
mplexity. Prentice-Hall, Englewood Cliffs, NJ, 1982
Stemmer WPC: The evolution of molecular computation Science 1995, 270:1510
Stemmer WPC: DNA shuffling by random fragmentation and reassembly: in vitro 
recombination for molecular evolution. Proc. Natl. Acad. Sci. U.S.A. 1994, 9
1:10747-10751
Boneh D, Lipton R, Dunworth C: Breaking DES Using a Molecular Computer. http
://theory.stanford.edu/~dabo/biocomp.html
Pool R: A boom in plans for DNA Comuting. Science 1995, 268:498-499
Guarnieri F, Fliss M, Bancroft C: Making DNA add Science 1996, 273:220-223
Roweis S, Winfree E, Burgoyne R, Chelyapov N, Goodman M, Rothemund P, Adlema
n L: A sticker based architecture for DNA computation. In Proceedings of the
 Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Ma
thematics and Theoretical Computer Science. Providence, PI: American Mathema
tical Society; 1996
Ma, RI, Kallenbach NR, Sheardy RD, Petrillo ML, Seeman NC Three-arm nucleic 
acid junctions are flexible. Nucleic Acids Res 1996, 14:9745-9753
Seeman NC: de novo design of sequences for nucleic-acid structural-engineeri
ng. J Biomol Struct Dyn 1990,8:573-581
Seeman NC et al.: The perils of polynucleotides: the experimental gap betwee
n the design and assembly of unusual DNA structures. In Proceedings of the S
econd Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Math
ematics and Theoretical Computer Science. Providence, PI: American Mathemati
cal Society; 1996
Du SM, Seeman NC: The construction of a trefoil knot from a DNA branched jun
ction motif. Biopolymers 1994, 34:31-37
Fu TJ, Tse-Dinh YC, Seeman NC: Holliday junction crossover topology. J Mol B
iol 1994, 236:91-105
Zhang Y, Seeman NC: The construction of a DNA truncated octahedron. J Am Che
m Soc 1994, 116:1661-1669
Seeman NC: Nucleic acid junctions and lattices. J Theor Biol 1982, 99:237-24
7
Winfree E, Yang X, Seeman NC: Universal computation via self-assembly of DNA
: some theory and experiments. In Proceedings of the Second Annual Meeting o
n DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretica
l Computer Science. Providence, PI: American Mathematical Society; 1996
Fu TJ, Seeman NC: DNA double crossover molecules. Biochemistry 1993, 32:3211
-3220
Felder RA, Boyd JC, Margrey K, Holman W, Savory J: Robotics in the medical l
aboratory. Clin Chem 1990, 36:1534-43
Wood MD, Franchetti JA: Laboratory automation using robotics and information
 management systems. Curr Opin Biotechnol 1993, 4:91-4
Ramsay G: DNA chips: state-of-the art. Nat Biotechnol 1998, 16:40-4
Cheung VG, Morley M, Aguilar F, Massimi A, Kucherlapati R, Childs G: Making 
and reading microarrays. Nat Genet 1999, 21:15-9

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

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