DNA分子计算机

DNA分子计算机 DNA F0503028 5050309118 张思宇 摘要 ： 本文介绍了DNA计算机的起源和发展以及研究现状，简要阐述了DNA计算机的计算原理，进而说明了其显著的优势，同时也指出了现阶段制约其发展的瓶颈。对其的应用前景进 行了展望。 关键词：DNA计算机 分子计算机 并行计算 汉密尔顿回路 引言： 随着社会和科学技术的发展，许多新工程领域中的复杂巨系统不断出现。 在这些复杂巨系统的研究过程中，各种各样的非线性问题、形形色色棘手的NP完全问题处处可见，使得电子 计算机解决这些NP2完全问题、复杂的非线性等问题难度很大，甚至无能为力! 其原因主要有两点： (1) 与要解决的实际问题相比，电子计算机的运算速度太慢； (2) 目前的电子计算机存储信息的容量太小。 另外， 电子计算机在制造工艺上将很快达到0。 06μm 这个极限值。 基于这些原因，迫使科学 家们寻求其它技术来提高运算速度与信息存储等问题。 于是，人工神经网络计算机模型、量子 计算机模型、光子计算机模型以及DNA 分子、蛋白质分子计算机模型相继产生，其中DNA 计算机模型在近几年内倍受科学界的关注，发展神速。 一、DNA计算机的起源及发展 在上个世纪六七十年代。很多科学家都提出了利用DNA进行计算的构思。比如1970年牛津大学就曾提出过DNA计算机的蓝图。利用DNA本身依靠A ，T ，G ，C四个独立碱基构成的特点。形成一个四进制组合。但在当时整个计算机产业都还在初期发展阶段。这个设 计蓝图只是摆在实验室里而无法得到贯彻。 1994年，L。Adleman首次在《Science》公布了DNA计算机的理论，利用DNA计算解决了图论中的Hamilton回路问题(HPP)，并成功地进行了实验。这一成果迅速在国际上产生了巨大反 响，由此开创了DNA计算机研究的新纪元。 紧接着，Lipton论证了DNA计算可解决完全性问题。 1995年Winfree提出细胞自动机理论，1998年在生物实验中用自组织DNA对细胞自动机进行了操作。 1996 年，来自世界各地的200 多名专家汇聚美国普林斯顿大学，共同探讨并肯定了DNA 计 算机的可行性。 1996年，Frank等提出了基于DNA分子的二进制加法。 1997年，Qi Ouyang 等人提出求解一个图的最大团问题的DNA算法，并且用生物实验在小规 模的图上实现了DNA算法。 1999年Bernard用表面化学方法完成正有理数加法的计算。解决问题的思想具有一般性，对DNA计算的研究有指导意义 2000年，日本的Kensaku用DNA分子的二级结构进行计算，他们用生物技术求解了一个6个变量10个子句的逻辑。 2001 年11 月， Benenson在Nature 杂志上报道了一种由DNA 分子和相应的酶分子构成的DNA 生物计算机，体积只有一只试管的1/16 ，每秒可执行10 亿次作业，准确率高达99。8 % ，这 种DNA 计算机也是世界上第一部输入输出、软件和硬件均由生物分子组成的有图灵机功能的可 程序自律计算机器， 是DNA 计算机研究的标志性重大进展 在Benenson 的文章中，我们看到了计算的完备性。这种完备性后来有不少理论上的证明， 表明理论上存在可编程的DNA 计算机，而且任何图灵机能进行的计算都可以由DNA 计算机来实现，而且DNA 计算机很可能有能力实现在图灵机框架下不能实现的功能。 2001 年，美国科学家利用简单的分子生物学操作进行DNA 计算，为一个有24 个变量、100 万种可能结果的数学难题(3SAT 问题) 找到了答案 ，这是迄今利用非电子化计算手段解决的最复 杂数学问题。 2002 年2 月，日本奥林巴斯公司与东京大学联合开发出全球第一台能够真正投入商业应用的 DNA 计算机，用于基因诊断。该计算机由分子计算组件和电子计算部件两部分组成，前者用来 计算分子的DNA 组合，以实现化学反应，搜索并筛选出正确的DNA 结果；而后者则对这些结果进行分析，并且能将原来人工分析DNA 需要的3 天时间缩短为6 个小时。 2003年8 月18 日世界首台互动式DNA 游戏计算机“MAYA”面世，以构成生命基石的DNA 为基础，用复杂的DNA 分子反应作为逻辑通道进行数据处理并实现具体的游戏程序。在与人 类的百场“拼字游戏”较量中，该计算机创下百战百胜的不败记录 2004年1月29日一条震动TT业界的消息传出：上海交通大学生命科学研究中心和中科院上海 生命科学院营养科学研究所己经在试管中完成了中国DNA计算机的雏形研制工作。 二、DNA计算机的计算原理 DNA 计算的核心问题是将经过编码后DNA 链作为输入，在试管内或其它载体上经过一定 时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物中能得到全部的解空间。 在DNA 计算系统中，DNA 分子中的密码作为存储的数据，当DNA 分子间在某种酶的作用下瞬间完成某种生物化学反应时，可以从一种基因代码变为另一种基因代码。 如果将反应前的基因代码作为输入数据，那么反应后的基因代码就可以作为运算结果。 2．1生物学方面 2．1．1计算流程 DNA 计算的基本思想是:利用DNA 特殊的双螺旋结构和碱基互补配对规律进行信息编码， 把要运算的对象映射成DNA 分子链，在生物酶的作用下，生成各种数据池(data pool) ，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。 最后，利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、 磁珠分离等，检测所需要的运算结果。 这样，通过对DNA 双螺旋进行丰富的精确可控的化学 反应，包括标记、扩增或者破坏原有链来完成各种不同的运算过程，就可能研制成一种以DNA 作为芯片的DNA 计算机。 随着人们对DNA 计算机研究的不断深入，用DNA 计算所对应的可控生化反应以及PCR 扩增技术，特别是关于检测技术的不断提高，生物芯片技术的不断成熟， 必将改进诸如以Adleman 为首的试管实验的方法与步骤，或者改进近期关于表面研究技术等， 但有一个基本点是不变的，那就是DNA 计算是充分利用生物酶、蛋白质，特别是DNA 分子的特性以及DNA 分子中海量的密码信息来进行可控的生化反应实现计算这个最基本的原理。 2．1．2酶的操作 DNA 串可作为译码信息， 酶可看作模拟在DNA 序列上的计算，主要的酶操作有以下几 种: 限制内切酶(rest riction endonudease) ，它识别链中特定的短序列，并在该位上将其“切割”， 用作分离算子。 结合酶(ligase) ，它把刚切过的DNA 黏端与其它链搭在一起或“连接”在一起，称为接合 反应，可作为绑结算子。 此外还有转移酶( terminal t ransferase) 、外切核酸酶(exonucleases) 和修饰酶(modifying 2．2数学原理方面 enzymes)等。 2．2．1针对NP问题的基本解决过程 NP问题是现阶段DNA计算机解决起来最得心应手的一类问题。 自从Adleman 的工作以后，用DNA 计算能解决的数学问题的种类迅速增长。 以Adleman解决的有向Hamilton回路问题(HPP)为例。 对于如图1所示的7个节点的有向图，计算步骤如下： (1)问题的编码及输入，每个节点的编码OI (I=0，1，?，6)长 度为20bp(base pair)，保证编码是可识别和唯一的。 (2)生成一个通过图的随机路径集，通过温度控制DNA 链接酶溶液来实现。 (3)搜索出以V0开始V6结束的路径集，通过以O0O6作引 物的聚合酶链反应。 (4)搜索出具有6个边的路径集，层析分离，3%～5%琼 脂糖凝胶。 (5)搜索出不重复边的路径集，生物素亲和层析磁珠分 离。 (6)选择出最短路径，电泳分离，取分子量最小者。 图1 自从Adleman 的工作以后，用DNA 计算能解决的数学问题的种类迅速增长。 Adleman 和Lipton 的发表后，很多研究人员提出了解决各种NP - Complete 问题的DNA算法，研究情况如表1 所示。 最初DNA计算只是应用在NP问题的解决。近几年来，关于DNA代数运算上的研究进展 也比较显著。 Roop 和Wagner 证明，若没有时间限制，Lipton 模型能处理任何计算问题 。并说明了DNA 计算机存在许多可能的结构。 2．2．2 DNA 的代数结构 构成DNA 的四元素能天然地形成数学上的一个良好的代数结构———域。 四元素集Σ= {A ， G，C ，T} ， 可按下图的两种代数运算加法“ + ”和乘法“ * ”，构成了一个四元域，实际上加法运算表为四元素A ，T ，G，C 所构成的双螺旋链的阵列。 此外，如果给这四个元素分配如下一个四进制编码 T ?00 ?04 ，A ?11 ?34 C ?01 ?14 ，G?10 ?24 它们就能将一个DNA 单链转换为熟悉的二进制编码。 表2 2．2．3四则运算 在DNA 计算机运算系统的研究中，首先取得突破性工作的是Frank 等人 。 Frank 等运用位置算子、位置转移算子和位节符等概念，用类似于电子计算机中的位数交换(bit2flipping) 方法， 完成了二进制数的存取与进位，创造性地完成了对DNA 分子生物运算过程的构造与控制。 他们给出了DNA计算系统中的正有理数的加法运算，他们工作中最为关键的贡献是解决了加法 的进位问题。 图2 一种DNA 计算的矩阵乘法运算模型也已在文献中给出。 在文献中， 作者给出了基于DNA计算模型的布尔矩阵和正实数矩阵乘法的计算方法。 图3 这种新技术及分析问题的方法能够促进基于DNA 技术来解决更多具有挑战性的组合问题。 有关这方面较为详细的内容参见文献。 目前关于负数的DNA 计算系统中的表示问题、减法运算、除法运算等尚未解决，这些都 是DNA 计算机研制过程中必须要解决的问题 2．2．4逻辑运算 我国国内在DNA计算机方面的研究开展得也比较广泛，华中科大今年发表了很多这方面的 论文，其中有提出对DNA计算机中DNA分子逻辑门设计： 与门示意图 非门示意图 三、DNA计算机的优势 3．1强大的并行计算能力 数百万亿个DNA 分子可在一个狭小的表面区域通过生物化学反应来实现运算，相当于大 批的DNA 计算机并行操作。在Adleman 的实验中，有向路径的分子数为10 14的量级，DNA 20计算的一些操作，如连接运算(ligation) 已达到每秒10个操作，而目前的超级计算机的处理速 12度仅为每秒10个操作。 DNA计算机在一周的运算量相当于所有电子计算机从问世以来的总 运算量。 3．2海量存储能力 3 DNA 作为信息的载体其贮存的容量非常之大，1m的DNA 溶液可存储1 万亿亿的二进制数据，远远超过当前全球所有电子计算机的总存储量。 12DNA 存储信息密度为每一立方纳米存储1 个字节，而现在计算机的存储密度为每10立 方纳米存储1个字节。 21一克DNA 所能存储的信息量( > 10 bits) ，估计可与1 万亿张普通CD 光盘(700M) 相当，存储密度是通常使用磁盘存储器的1 000 亿到10 000亿倍。 3．3极低的能耗 919现行电子计算机每焦耳执行10 操作，而DNA计算机每焦耳执行2 ×10操作，比前者能量 10效率高出10倍。 3．4抗电磁干扰能力强因分子信息通路不靠电信号控制逻辑开关，所以不受电磁干扰的影 响，并且具有生物分子固有的自我修复能力，可靠性高 3．5丰富的资源 四、现阶段DNA计算机面临的问题 4．1单分子技术与超大规模的并行性之间的矛盾 我们认为DNA 单分子的操纵技术将对DNA 计算机的发展起到重要作用。但是DNA 计算机的超级计算能力来源于超大规模的DNA 分子数量。既要进行单分子操作又要维持超大规模 数量的计算分子，是一个难以解决的矛盾。不过我们认为并不是DNA 计算的每一步都需要单分子技术，相信这个问题将来能够解决。 4．2人机界面 一直以来，如何使数学问题转化为DNA表达并正确输入以及如何从大量的反应产物中更有 效率的提取出最优解是困扰着DNA计算机发展的一大难题。 从目前来看，发展传统计算机和DNA计算机杂合是一个较为简单易行的途径。所以也有人认为， DNA 计算机至多只能起到一个运算器的作用，即使如此，这种传统计算机与DNA 计算机互补所获得的计算也将产生巨大影响。而且，随着技术的发展，DNA计算机的输入输出也许可以和 人工神经网络结合发展。 五、DNA 计算机的几种主要形式 5。 1 试管DNA 计算机 这是目前大部分DNA 计算机的工作形式。其技术核心是进行并行反应的分子游离在液体 中。反应物，中间产物和输出分子都混杂在一起。需要有专门的步骤把输出产物分离出来，分 离方法有琼脂糖电泳，毛细管电泳，高压液相，液质联用质谱等。 5。 2 表面计算 Wisconsin 大学的研究人员把DNA 计算的所有可能的结果附着在固体表面上，然后通过系 列的杂交和酶切来得到最后的答案。与试管计算相比，表面计算有不少优点，包括与硅技术的 匹配性。表面计算、芯片技术、微型化技术以及纳米技术等技术的综合可能是DNA 计算机实用化的必由之路。 5。 3 杂合计算机 这种DNA 计算机实际上是电子计算机与具有高度并行运算能力的DNA 计算单元结合而成。我们认为这是比较可行的第一代实用型DNA 计算机。电子计算机的功能是控制单元(控制部) ，在电子计算机与DNA 计算单元(计算部) 中间有自动化的DNA 分子加工部。 5。 4 生物膜系统 即所谓的P 系统，尚处于理论探讨阶段。 5。 5 细胞式计算机 尚处于理论探讨阶段。即使单细胞生物也在执行着复杂而有序的分子计算过程。高等细胞在基 因表达过程中的splicing and linking 以及后续的并行处理过程，与电子计算机中的数据结构化过 程没什么两样。 六、DNA计算机的巨大意义 6．1由于DNA 计算机的速度惊人，使得目前的密码系统对于DNA 计算机而言已经失去意 义。 数据加密与解密， 这是超级计算机应用的一个重要领域， 美国的研究者提出了用DNA 计算机破译美国政府为了保护某些重要数据加密DES (Data Encryption Standard)的。 这 15一标准加密的信息， 其代码依赖于72×10个密钥中的一个， 而DNA 计算机由于可以同时试验所有的密钥， 并找到正确的一个， 预计， 对于一个高度自动化的DNA 计算机， 解决 这个问题只需2 个小时。 6．2 DNA 计算机的研制对理论科学的研究具有无法估量的意义，特别是数学、运筹学与计 算机科学。 这是因为，在理论研究中许许多多的困难问题在DNA 计算机的面前可能显得非常 简单，如大数学家Erdos 认为人类要解决Ramsey 数R (5 ， 5) ， R (6 ， 6)是非常困难的。 然而，若用DNA 计算机来解决可能在几个小时，甚至有望在几分钟内得到解决。 6．3 P = N P ? 这个著名的数学难题有望得到彻底的解决，进而使人类在计算问题上有一个 大的飞跃，NP2完全问题不再像现在这样困扰科学家们。 许多工程技术问题的研究会大踏步的 向前飞跃。 6．4 DNA 计算机必将极大地促使非线性科学、信息科学、生命科学等的飞速发展。 事实上，在DNA计算系统中，非线性问题与线性问题几乎是一样的。这些问题的解决与发展必将导 致诸如图像处理、雷达信号处理等巨大的发展、蛋白质优化结构的更深层认识乃至第二遗传密 码的解决；也必将促使诸如量子科学、纳米科学等得到巨大的发展。 6．5 DNA 计算机的研制成功，对考古学、生态科学与地球科学等意义更为重大，特别是 DNA 计算机时代的天气预报几乎准确无误。 七、DNA计算机的应用 7．1 DNA 计算与遗传算法的融合 遗传算法( GA) ，用于模拟生命的自适应和进化，被用于设计好的机器和编制进化的计算 机程序。由于常规GA 用于实际问题，尤其是处理复杂的、混淆的许多任务问题时不够灵活， 且计算速度慢，一些学者提出了基于DNA 机理的改进的GA。 如，带有双串DNA 和GA 用于促进DNA 复制的非对换变异；类似DNA 编码的系统描述用于各种进化系统细胞特定化的模 型。 在细胞特定化的过程中，每个细胞具有相同的DNA。 硬件建模和计算机仿真显示了细胞 特定化具有自组织特性。 另外，还提出了基于生物学DNA 编码方法的GA。 这种方法具有DNA 染色体中的重复性和基因表达的重复性，并使交叉和变异操作变得容易，利用生物学DNA 的发展机理可实现知识的灵活表达。 DNA 转录、病毒DNA 和酶操作也可用这种DNA 编码来实现。 还有学者将DNA 编码方法与伪细菌GA ( PBGA) 相结合。 同时，为了避免在DNA 计算中，由于核酸碱基之间化学反应带来的误差，一些学者提出了用于搜索DNA进化计算中好的DNA 译码算法。 7．2 DNA 计算与神经网络的融合 生物的神经组织的生成和功能受DNA 遗传信息作用，故DNA 遗传信息可用于神经网络的 建模和优化。一种采用DNA 序列译码的框架被用于建立神经网络模型。 这种神经网络模型与采用常用CODE- 4 译码框架的神经网络相比能更好地预测分开DNA 序列的topoisomerase 可能性，且该网络大小是后者的1/ 4 ，因而该神经网络模型的参数数目减少了近75 %。 有的学者分析研究了采用DNA 译码的推理网络的复杂时空行为，该推理网络是由外部驱动的推理处 理元件或带有量子化相互作用的神经元耦合组成，相互作用的神经元是由分子生物学的遗传信 息译码，即根据DNA 分子中的四个不同符号来模拟。 这种将分子生物学和DNA 分子遗传信息译码与神经网络进行结合的研究有助于促进分子计算和学习机的发展。 7．3 DNA 计算与模糊系统融合 模糊系统在许多领域中已获得成功的应用，但对于复杂的多输入多输出模糊系统目前仍缺 乏有效的设计方法。 虽然常规GA 能用于获取模糊控制规则，但有时难以胜任复杂系统，如多 输入多输出系统的优化工作。 所以一些学者提出了基于DNA 编码机理的GA 并用于多变量模糊系统的优化。 它能用于输入变量的选择和映射函数参数的调整，从而自动获取模糊控制规则。 并且，病毒和酶操作也用于这种DNA 编码方法。 机器人运动控制的研究中初步显示了这种方 法的可行性。 7．4 DNA 计算与混沌的融合 一种获取对应于所需DNA 算法的反馈网络的系统方法被提出，此时混沌系统可看成包含 待处理信息的一个试管。 按照DNA 计算框架，利用混沌动态性的丰富本质特性来有效地产生 和处理二进制编码序列，进而得到问题的解答。 八、DNA 计算机的展望 虽然，科学家们在DNA 计算机研究方面取得了很大的进展，但还有许多困难和问题需要广大 科研工作者努力去克服与解决，以后的研究将往以下一些方面发展: (1) 继续研究探索其它新的DNA 计算及模型。 (2) 探索各种类型可由DNA 计算解决的NP 问题。 (3) 定义和研究DNA 计算的复杂性、生物复杂性和可实现性的衡量尺度。 (4) 探索一种分子高级语言所必须的基本生物操作。操作易于实现，易于自动化，易于消除或减 少差错和易于优化操作过程。 (5) 开发适合于分子生物计算新的问题求解工具和程序。构造基于DNA 求解问题的装置并使之 自动化。研究未来DNA 计算机的可行性。 (6) 研究DNA 计算与各种软计算的融合、集成和结合。探索DNA 计算在工程和智能控制中的应用。比如在常规的遗传算法上进行以下改进: (a) 编码改进，由{0 ，1} 二进制编码改成DNA 的{A ， T ，C ，G}编码； (b) 操作改进，由单点交叉发展成多点交叉、标准交叉，增加反转技术，改进替代策略等，同 时研究基于DNA 机理的学习方法，并用于模糊系统和神经网络的生成和优化设计。 (7) 开发可利用的各种DNA 芯片，以用于计算机、半导体和光化学合成等微加工技术。 (8) 在DNA 计算实验中，如何选择实际操作参数的数目、个体操作的速度、个体操作和序列操 作的可靠性、信息载体的稳定性及一个实验中连续操作的数目。 (9) 制成与电子相结合的计算机，在这种计算机中，每部分完成自己适合的任务，并行任务用 DNA来计算，而固有的串行工作由硅芯片来完成，同时还应该开发一种高级分子编程语言。 如今出现的DNA 计算机，将彻底改变计算机硬件性质，改变计算机的基本运作方式，其 意义极为深远。人们完全可以做这样一番想象， DNA 计算机一旦实用，那么，真正的“人机 合一”就会实现。到那时，人们不再需要电脑，人们真正需要的只是一个接口。DNA 计算机蕴含的理念不仅可以使计算方式进化，而且可以使人类的大脑思维进化。 21世纪是计算科学的世纪，21世纪是生物科学的世纪，由此我们可以无限乐观的期待DNA计算机时代的到来。这将是人类社会的一个新纪元！ 参考文献： 1．《DNA计算的原理和模型》 刘西奎，李 艳，许 进， 《计算机工程》，2002年6月 2．《DNA计算机原理进展及难点?生物计算系统及其在图论中的应用》 3．《DNA计算机的分子生物学研究进展》 4．《DNA计算机理研究及展望》 5．《DNA计算机能否引发新一轮信息革命》 6．《DNA计算机原理现状及发展》 7．《DNA计算原理及系统分析》 8．《发夹结构在建立DNA计算机中的应用》 9．《关于DNA计算的基本原理与探讨》 10．《深入浅出DNA分子计算》 11．《生物分子计算机》 12．《生物计算机_试管里的奇迹》 13．《试管里的计算机》 14．《DNA计算机实现自我驱动》 15．《DNA计算研究的新进展》 16．《DNA计算与背包问题》 17．《DNA计算与数据加密标准》 18．《IT史话DNA计算机发展之路上》 19．《生物计算机DNA中蕴藏的超级计算》 20．《有向最短哈密尔顿路问题的DNA算法》 21．《运行于磁珠表面的可编程DNA计算机》 22．《21世纪是信息科学合成化学和生命科学共同繁荣的世纪》