今日动态

生物通首页 > 今日动态 > 正文

DNA计算（下）

时间：2001年2月4日
来源：

编辑推荐：

广告
   X   

强大的运算能力

    普通台式计算机能以每秒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连接反应里居然蕴藏着如此巨大的计算能力。那么在细胞中进行的其他酶促反应是否也如此呢？转录、翻译调控对细胞生命行为起着巨大的作用，在它们的背后是否存在着某种计算机制呢？这些机制又能否应用到科学计算中去呢？都将有待于分子生物学与计算机学的进一步发展与合作。

参考文献

  1. Feynman RP: There’s plenty of room at the bottom. Miniaturization. 1961:282-296
  2. Adleman L: Molecular computation of solutions to combinatorial problems. Science 1994, 266:1021-1024
  3. Friedman Y: DNA Computers. http://dna2z.com/dnacpu/dna.html
  4. Gibbons A, Amos M, Hodgson D: DNA computing. Curr. Opin. Biotech. 1997, 8:103-106
  5. Garey MR, Johnson DS: Computers and Intractablility. Freeman, San Francisco, CA, 1979
  6. Ouyang Q, Kaplan PD, Liu S, Libchaber A: DNA solution of the maximal clique problem. Science 1997, 278:446-449
  7. Gifford DK: On the path to computation with DNA. Science 1994, 266:993-994
  8. Amos M, Gibbons A, Hodgson D: Error-resistant implementation of DNA computations. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  9. Jonoska N, Karl SA: A molecular computation of the road coloring problem. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  10. Lipton RJ.: DNA solution of hard computational problems. Science 1995, 268:542-545
  11. Watson JD, Hpkins NH, Roberts JW, Steitz JA, Weiner AM: Molecular Biology of the Gene Benjamin/Cummings, Menlo Park, CA, ed.3, 1987
  12. 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; Atlanta. Philadelphia: SIAM; 1996:458-467
  13. Boneh D, Dunworth C, Lipton RJ, Sgall J: Making DNA computers error resistant. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  14. James KD, Boles AR, Henckel D, Ellington AD: The fidellity of templated-directed oligonucleotide ligation an its relevance to DNA computation. Nucleic Acids Res. 1998, 26:5203-5211
  15. Liu Q, Guo Z, Condon AE, Corn RM, Lagally MG, Smith LM: A surface-based approach to DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  16. Corn RM, Smith LM, Condon AE, Lagally MG: DNA Computing and Informatics at Surfaces. http://www.corninfo.chem.wisc.edu/writings/DNAcomputing.html
  17. Guo Z, Guilfoyle RA, Thiel AJ, Wang R, Smith LM: Direct fluorescence analysis of genetic polymorphisms hybridization with oligonucleotide arrays on glass supports. Nucleic Acids Res 1994, 22:5456-5465
  18. Linial M et al.: On the potential of molecular computing. Science 1995, 268:481-483
  19. Papadimitriou CH, Steiglitz K: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982
  20. Stemmer WPC: The evolution of molecular computation Science 1995, 270:1510
  21. Stemmer WPC: DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution. Proc. Natl. Acad. Sci. U.S.A. 1994, 91:10747-10751
  22. Boneh D, Lipton R, Dunworth C: Breaking DES Using a Molecular Computer. http://theory.stanford.edu/~dabo/biocomp.html
  23. Pool R: A boom in plans for DNA Comuting. Science 1995, 268:498-499
  24. Guarnieri F, Fliss M, Bancroft C: Making DNA add Science 1996, 273:220-223
  25. Roweis S, Winfree E, Burgoyne R, Chelyapov N, Goodman M, Rothemund P, Adleman L: A sticker based architecture for DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  26. Ma, RI, Kallenbach NR, Sheardy RD, Petrillo ML, Seeman NC Three-arm nucleic acid junctions are flexible. Nucleic Acids Res 1996, 14:9745-9753
  27. Seeman NC: de novo design of sequences for nucleic-acid structural-engineering. J Biomol Struct Dyn 1990,8:573-581
  28. Seeman NC et al.: The perils of polynucleotides: the experimental gap between the design and assembly of unusual DNA structures. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  29. Du SM, Seeman NC: The construction of a trefoil knot from a DNA branched junction motif. Biopolymers 1994, 34:31-37
  30. Fu TJ, Tse-Dinh YC, Seeman NC: Holliday junction crossover topology. J Mol Biol 1994, 236:91-105
  31. Zhang Y, Seeman NC: The construction of a DNA truncated octahedron. J Am Chem Soc 1994, 116:1661-1669
  32. Seeman NC: Nucleic acid junctions and lattices. J Theor Biol 1982, 99:237-247
  33. Winfree E, Yang X, Seeman NC: Universal computation via self-assembly of DNA: some theory and experiments. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996
  34. Fu TJ, Seeman NC: DNA double crossover molecules. Biochemistry 1993, 32:3211-3220
  35. Felder RA, Boyd JC, Margrey K, Holman W, Savory J: Robotics in the medical laboratory. Clin Chem 1990, 36:1534-43
  36. Wood MD, Franchetti JA: Laboratory automation using robotics and information management systems. Curr Opin Biotechnol 1993, 4:91-4
  37. Ramsay G: DNA chips: state-of-the art. Nat Biotechnol 1998, 16:40-4
  38. Cheung VG, Morley M, Aguilar F, Massimi A, Kucherlapati R, Childs G: Making and reading microarrays. Nat Genet 1999, 21:15-9

热点排行
生物通微信公众号
微信
新浪微博
我要投稿

返回顶部

生物通 版权所有