生物计算机时代即将来临

2014年.第29卷.第1期生物计算机研究进展AdvancesinBiologicalComputer*基金项目：973项目（2013CB329601,2013CB329602），国家自然科学基金重大仪器专项（61127005），国家自然科学基金项目（60974112,30970960）修改稿收到日期：2014年1月5日【摘要】生物计算机是以核酸分子作为“数据”，以生物酶及生物操作作为信息处理工具的一种新颖的计算机模型。生物计算的早期构想始于1959年，诺贝尔奖获得者Feynman提出利用分子尺度研制计算机；1994年，图灵奖获得者Adleman提出基于生化反应机理的DNA计算模型；在生物计算机方面突破性工作是北京大学在2007年提出的并行型DNA计算模型，将具有61个顶点的一个3-色图的所有48个3-着色全部求解出来，其算法复杂度为359，而此搜索次数，即使是当今最快的超级电子计算机，也需要13217年方能完成，该结果似乎预示着生物计算机时代即将来临。文章重点介绍了生物计算机的产生背景及意义；DNA计算机，特别是中州I-型DNA计算机的基本原理、计算方法与步骤；DNA计算机的研究进展，特别指出在密码分析与破译等领域的应用；分析了DNA计算机的能力，指出了研究中的难点、发展趋势，最后对我国生物计算机发展提出了一些建议。【关键词】生物计算机，非枚举型DNA计算机，并行型DNA计算机，大规模型DNA计算机，密码分析与破译，研究进展，发展建议DOI10.3969/j.issn.1000-3045.2014.01.007文/许进北京大学信息科学技术学院北京100871生物计算机时代即将来临*1生物计算机产生背景与意义计算工具是人类文明生活中不可缺少的工具之一。伴随着人类文明程度不断进步和发展，计算工具也随之进步与发展。人类文明时代可分为石器时代、铁器时代、蒸汽机时代、电气时代以及信息时代等阶段。在这几个阶段里，计算工具也编者按超级计算是国家最核心的基础能力之一。与电子计算机相比，生物计算机在存储、计算、效能等方面超乎想象的巨大潜力，对我国未来的国家安全和基于“大数据”的经济社会发展具有十分重大的战略意义。本刊特推出专栏，从多侧面评述该领域的进展，希望其能引起读者和相关决策者的关注。42院刊生物计算机时代即将来临历经了由简单到复杂、从低级到高级的不同演化过程，从“结绳记事”中的绳结、算筹、算盘、计算尺、机械计算机，直到当今的电子计算机，它们在不同的历史时期发挥了各自的历史作用。电子计算机在其发展过程中，惊人地遵从摩尔定律[1]，为人类文明社会的发展做出了巨大贡献。但是，半个世纪以来，科学家们却一直在考虑新型计算机模型的研制，特别是2011年，在纪念图灵诞辰100周年的时候，就曾面向全世界征集超越图灵机的新型计算模型。追其原因，主要有两点：第一，电子计算机的工艺制造技术即将达到极限，如著名的理论物理学家Kaku在2012年预言，10年内电子计算机的工艺制造技术将达到极限；第二，由于图灵机模型所致，电子计算机一直不能处理规模较大的NP-完全问题。在探索非传统的新型计算机模型研究中，相继提出了仿生计算（人工神经网络、进化计算、PSO计算等）、光计算、量子计算及生物计算等。而目前所有的仿生计算均依靠电子计算机来实现；光计算的计算模型就是图灵机模型，但实现的材料是光器件[2-4]，因此，很难超越当今的电子计算机；量子计算在处理NP-完全问题时的最好结果是：若在图灵机下算法复杂度是n，则量子计算可将复杂度降低为n[5,6]。这就是说：量子计算模型实际上尚未超越图灵机模型。生物计算是指以生物大分子作为“数据”的计算模型，主要分为3种类型：蛋白质计算、RNA计算和DNA计算。蛋白质计算模型的研究始于20世纪80年代中期，Con-rad首先提出用蛋白质作为计算器件的生物计算模型[7]。1995年，Birge发现细菌视紫红质蛋白分子具有良好的“二态性”，拟设计、制造一种蛋白质计算机[8]。进而，Birge的同事，Syracuse大学的其他研究人员应用原型蛋白质制备出一种光电器件,它存贮信息的能力比目前电子计算机的存贮器高300倍,这种器件含细菌视紫红质蛋白,利用激光束进行信息写入和读取[9]。该蛋白质计算模型均是利用蛋白质的二态性来研制模拟图灵机意义下的计算模型，应属于纳米计算机“家族”的一员。不同于蛋白质计算，RNA计算与DNA计算是利用生化反应，更确切地讲，是以核酸分子间的特异性杂交为机理的计算模型。由于RNA分子不仅在实验操作上没有DNA分子容易，而且在分子结构上也不如DNA分子处理信息方便，故目前对RNA计算的研究相对较少，有兴趣的读者可参见文献[10]和[11]。所以，近20年来，蛋白质计算与RNA计算少有进展，但DNA计算发展很快。故本文只介绍DNA计算与DNA计算机。DNA计算是一种以DNA分子与相关的生物酶等作为基本材料，以生化反应作为信息处理基本过程的一种计算模式。DNA计算模型首先由Adleman博士于1994年提出[12],它的最大优点是充分利用了DNA分子具有海量存储的能力，以及生化反应的海量并行性。因而，以DNA计算模型为基础而产生的DNA计算机，必有海量的存储能力及惊人的运行速度。DNA计算机模型克服了电子计算机存储量小与运算速度慢这两个严重的不足，具有如下4个优点：（1）DNA作为信息的载体，其贮存的容量巨大，1立方米的DNA溶液可存储1万亿亿的二进制数据，远远超过当前全球所有电子计算机的总储存量；（2）具有高度的并行性，运算速度快，一台DNA计算机在一周的运算量相当于所有电子计算机问世以来的总运算量；（3）DNA计算机所消耗的能量只占一台电子计算机完成同样计算所消耗的能量的十432014年.第29卷.第1期生物计算机研究进展AdvancesinBiologicalComputer亿分之一；（4）合成的DNA分子具有一定的生物活性，特别是分子氢键之间的引力仍存在。这就确保DNA分子之间的特异性杂交功能。由此可见，DNA计算的每项突破性进展，必将给人类社会的发展带来不可估量的贡献。第一，DNA计算机的研究在国防领域具有极为重要的意义。由于DNA计算的巨大并行性所导致的惊人速度，使得目前的密码系统对于DNA计算机而言已经失去意义。这就意味着，哪个国家在DNA计算机的研制中首先取得成功，这个国家在军事信息领域必将占据领先地位；第二，DNA计算机的研制对理论科学的研究具有无法估量的意义，特别是针对数学、运筹学与计算机科学。这是因为，在理论研究中，许许多多的困难问题在DNA计算机的面前可能显得非常简单，如著名数学家Erdös认为人类要解决Ramsey数R（5，5）、R（6，6）是非常困难的。然而，若用DNA计算机，该问题将会很容易得到解决；第三，DNA计算机必将极大地促使非线性科学、信息科学、生命科学等的飞速发展，进而推动诸如图像处理、雷达信号处理等巨大的发展；蛋白质优化结构的更深层认识乃至第二遗传密码的解决、天气预报更准确乃至整个气象科学的巨大发展等；也必将促使诸如量子科学、纳米科学等的巨大发展。正是由于DNA计算机的上述重要意义，使得目前国际上关于DNA计算机的研究形成了一个新的科学前沿热点，正在极大地吸引着不同学科、不同领域的众多科学家，特别是生物工程、计算机科学、数学、物理、化学、激光技术以及信息等领域的科学家。2009年美国基金会启动超越摩尔定律的资助项目，主要用于资助DNA计算与量子计算。2DNA计算与DNA计算机的基本原理DNA计算是以DNA分子作为信息处理的“数据”，相应的生物酶或生化操作作为信息处理“工具”的一种新型计算模型。基于DNA计算模型研制的DNA计算机，与电子计算机在硬件、原理等方面均不相同。DNA计算模型的一般原理图，可简要地通过图1所示的框图来描述：输入的是DNA片断和一些生物酶以及所需要的试剂等，然后通过可控的生化反应，输出的是DNA片断，这些DNA片断就是所需问题的解。关于DNA计算机原理，我们以中州型DNA计算机模型为例给予说明。北京大学生物计算机研究组通过十几年的研究，建立了名为《中州I-型DNA计算机》硬件体系结构[13]，主要由4部分构成：存储系统、检测系统、运算系统及控制系统等，其中存储系统中含有“数据子库”及相应的探针子库；这4个系统之间的逻辑关系如图2所示。中州I-型DNA计算机具有一定的通用性，可用于密码分析及大规模NP-完全问题等的求解。用该DNA计算机求解，与电子计算机唯一类似的是，将所给问题映射到DNA计算机模式上去。DNA计算与DNA计算机的研究已有20年的图1DNA计算模型一般原理图图2中州I-型DNA计算机结构示意图44院刊历史，目前虽仍处于实验室阶段，但已能解决一些复杂的困难问题[14]。下面，我们首先给出一般在实验室利用DNA计算求解问题的具体方法步骤，然后给出中州I-型DNA计算机求解问题的步骤。一般用DNA计算模型求解步骤如下：第一步模型选择：针对问题，选择或建立DNA计算模型；第二步编程：在已有模型的基础上，进行编程；第三步编码：在DNA链的条数确定后，依据具体问题，建立相应约束条件（如解链温度值的约束，特异性杂交的约束，特别是要求链尽可能短等约束），进而进行编码；第四步合成DNA分子：对通过编码确定的DNA链，进行合成，并购置所需的生物酶以及相关试剂等；第五步建立计算平台：建立适应于生化反应、特异性杂交、无污染的良好生化操作环境；第六步实施计算：将所需DNA链、探针以及相关试剂等按照生化处理程序进行；第七步解的检测：通过PCR、测序、电镜，甚至光电等综合技术检测出所需要的解。中州I-型DNA计算机的计算模型已固定，且需要的DNA链已合成，计算平台等均已建立，故只需要如下3步：第一步编程：针对问题直接进行编程；第二步实施计算：将通过编程后确定的DNA链、探针以及所需试剂等注入运算系统，进行运算；第三步解的检测：利用计算机中的检测系统，将所需问题的解全部检测出来，并输出。限于篇幅，在此不赘述中州I-型DNA计算机的体系结构以及DNA计算的基本原理，相关内容可参见文献[15-22]。3DNA计算机研究进展DNA计算机的研究可分为两大方面：（1）用于纳米机器人的研制。这方面的主要工作是充分利用DNA分子之间的特异性杂交开展的自组装技术。其研究成果重点应用于诸如疾病诊断治疗的自动化问题、癌细胞的消除等。如在2004年，以色列科学家在理论与实验上均证明了：DNA计算机是进行疾病诊断治疗的新有力手段[23-24]；（2）用于信息处理的计算机研制。主要研究快速实用化的、至少在某些方面超越电子计算机的新型计算机。从1995年起，由美国发起的生物计算机国际会议每年一届，一直延续至今。2006年，由中国、美国、日本以及一些欧洲国家发起了一个规模更大的国际生物计算机会议。该会议每年一届，已经召开了8届。其中第四届大会由北京大学承办，许进教授5次任生物计算机国际大会主席。此外，在生物计算机方面发表的学术论文数逐年呈指数上升，而且国际上已出版了多部生物计算机方面的学术专著。经过20年的研究，DNA计算机无论在理论方面，还是在硬件研制方面，都取得了极大进展。特别是在2007年，我国成功地建立了搜索次数可达359的并行型DNA计算机模型[14]。而且，近两年利用自组装技术，由DNA分子构成的几种重要结构实现的成功，也极大地缩短了DNA计算机走向实用的周期。这些都表明一个新型的信息处理工具——生物计算机的时代即将来临！目前关于DNA计算与DNA计算机方面的研究内容很多，其研究方向主要涉及诸如模型构建、编码、检测、控制技术等方面。另外，在诸如密码分析与破译，困难NP-完全问题求解上均有突破性的工作。下面，对生物计算机时代即将来临452014年.第29卷.第1期生物计算机研究进展AdvancesinBiologicalComputer国内外研究现状给予简要介绍。3.1DNA计算中模型构建研究进展1959年，诺贝尔奖获得者Feynman提出了分子计算的构想[25]；1973年，Ben