化学中的计算——dna计算的发展与模型概述

《化学中的计算——dna计算的发展与模型概述》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、化学中的计算型概述DNA计算的发展与模尹晓尧李非伯晓晨骆志刚左小磊国防科技大学计算机学院并行与分布重点实验室里事医学研宄院辐射医学研宄所中国科学院上海应用物理研宄所物理生物学研宄室电子计算机的发展给人类社会进步带来了极大的推动作用，但是随着电子计算机制造工艺趋于极限，人们迫切需要找到一种新的计算体系来满足口益增长的计算需求。DNA计算因其超强的信息存储、大规模的并行计算能力和超低的能耗而受到了广泛的关注。自1994年Adieman在实验室利用DNA完成了一个6顶点哈密尔顿路求解问题开始，各种计算模型纷纷涌现

2、。木文首先对DNA计算的基本原理和实验操作手段进行了简单的介绍，然后对DNA相关的理论进行了阐述，包括DNA计算屮序列编码设计的理论、DNA计算模型复杂度分析与通用计算能力的证明；在此基础上，对突破性的DNA计算模型进行了概括，进而根据实验操作的具体手段将所有已知模型进行了分类，按照类别进行了综述，并随后挑选了该类别中经典的模型进行更为直观的分析。更进一步，在文章的最后，结合笔者的工作对DNA计算领域的前景进行了展望。关键词：DNA计算;NP难问题;并行重叠组装模型;粘贴模型;剪接模型;DNATile组装;

3、牛.化信号;逻辑门;计算机研宄者们将计算问题划分为三类:容易、困难和不可计算。对于容易类的计算问题，目前的电子计算机可以轻易地胜任;但是对于网难类的计算问题，即我们常说的NP（nondeterministicpolynomial,非多项式吋间可解）问题时，随着问题规模的増大，计算所需要的时间呈指数级别増长，传统计算机难以维持。此外，随着计算机制造工艺的不断发展，芯片上集成的晶体管数量逐渐接近极限，量子效应越发明显，电子计算机的发展速度与计算需求之间的鸿沟进一步扩大。因此，科学家们致力于寻找其他全新的计算机结

4、构，试图有效地解决这些问题。DNA计算是一种以DNA分子与相关的某些生物酶作为基本材料，以某些生化反应为棊础的新的计算模式。其棊本思想是利用DNA分子特殊的双螺旋结构和碱基互补配对Watson-Crick原理，将所要处理的问题编码为特定的DNA分子，通过一系列的生物化学反应和基础的实验操作，来实现运算的过程，这种生物计算的思想开创了一种新的计算模式。DNA计算因为其超强的优势而受到了广泛的关注，具体来说：（1）高度并行性，DNA计算机在一周内的运算量相当于所有电子计算机问世以来的总运算量；（2）储存量大，D

5、NA作为遗传信息的载体其信息存储容量之大可达到一立方米溶液中存储一万亿亿比特的二进制数据，远远超过目前所有电子计算机的总存储量；（3）耗能低，DNA计算所消耗的能量只有一台电子计算机完成同样计算所消耗能量的十亿分之一。DN八计算思想的提出己经有了大半个世纪，早在1961年，FeynmanXll提出了分子计算的概念，但是由于受到当时的实验条件、材料、生物技术等方面的限制，他的构想并没有真正得以实现。人们对分子生物学理论的认识和研宂的深入，以及新的生物技术和实验方法的不断涌现，为分子计算的实现打好了基础。198

6、2年，提出了利用DNA分子构造各种简单构件的思想。1994年，八dlemanUl首次提出了哈密尔顿有向路问题的DNA分子生物计算方法，并成功地在装有DNA溶液的试管屮进行了实验，开创了计算科学的一个新领域，具有十分重大的意义，这一重大成果很快引起了数学、计算机、生物学等领域的研允者们的广泛关注。1995年，LiptcmM提出基于DNA计算求解可满足性问题的模型，将DNA序列映射为布尔矢量，通过一系列的溶液分离与合并操作，最终筛选出满足条件的解。Seemarin首次提出了利用DNA分子构成自组装Tile结构，

7、他利用其屮一种DXTile结构建立多种复杂的算法模型对于二维的自组装模型，Winfroo称其为“Tile自组装模型”，它是建立在Wang等皿提出来的Tile理论基础上的；1995年，Winfi、ee［10］提出利用DNATile自组装模型进行计算的重要思想，并证明了二维自组装模型有通用计算能力;2000年，Mao等［11］首次通过实验给出了自组装DNA计算模型求解累积异或运算的实现过程和方法。1997年，Ouyang等Uil提出了求解6顶点图的最大团问题的DNA计算模型，该方法通过分析原图的补图，利用酶切的

8、方法来缩小解搜索空间，并且对顶点的0和1进行了不同长度的编码，使得可以通过琼脂糖凝胶电泳测得的DNA序列的长度来判断最大团的大小。其后，EngX^l提出了一种基于DNA表面计算求解可满足性问题的计算模型。1997年，Hagiya等U41首次将单链0嫩分子形成的发卡结构用于Boolcanu-formula的学习问题，利用该结构实现丫分子的自动控制问题。Head等［15］首次使用质粒DNA模型求解了一个6顶点阁的最大