书名：生物计算
ISBN：978-7-115-66579-9
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 许 进
责任编辑 贺瑞君
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
生物计算是一种以DNA、RNA和蛋白质等生物大分子为数据的计算。本书较为深入地探讨DNA计算的各个方面，从基础理论到实验操作，再到解的检测，都囊括其中。同时，书中对RNA计算和蛋白质计算也进行了概述。全书共12章。其中，第1章～第4章详细介绍图与计算复杂性、生物计算数据、生物计算算子（酶与生化操作），以及在DNA计算中发挥关键作用的技术和方法。第5章重点阐述DNA编码理论与算法。第6章～第8章深入探讨枚举型、非枚举型、并行型等多种DNA计算模型的构建思路和优缺点。第9章与第10章介绍一些DNA计算在密码学、生物信息学、优化问题等领域的应用案例。第11章与第12章介绍RNA计算与蛋白质计算的相关理论与应用。这样的结构安排旨在为读者提供一个全面、系统的生物计算知识框架。
本书适合图论与算法、分子生物学、计算机科学、生物信息学及人工智能等领域的科研人员、高等学校师生，以及对生物计算感兴趣的读者阅读。
1996年，我正沉浸于用人工神经网络（Artificial Neural Network，ANN）来求解图论中的NP完全问题，如旅行商问题、图着色问题、哈密顿问题等。那时的我希望建立用ANN求解这些难题的快速算法，带领博士研究生们发表了不少相关学术论文。有一天，我的一位博士研究生告诉我，她在图书馆读到一篇发表在Science上的文章，文中介绍了利用脱氧核糖核酸（Deoxyribonucleic Acid，DNA）分子求解有向哈密顿路径问题的方法。我听后很兴奋，认为这可能是求解NP完全问题的一种新途径，一定要学习学习，于是急忙去图书馆将文章复印下来开始阅读。然而，我阅读此文时茫然了——因为我在中学没有学习过生物学课程，所以完全无法理解文中的生物学原理和实验设计。
从那时起，我便下定决心：必须好好学习生物学，在生物计算领域有所作为。于是，我从零开始，先系统地学习了中学的生物学知识，随后深入钻研了分子生物学、生物化学等课程。历经十余年的不懈努力，我在利用DNA计算求解NP完全问题的过程中，已能够自如地独立完成数学计算模型构建、生物实验操作设计、解的检测等关键环节。
过去30余年中，DNA计算经历了从枚举型到非枚举型，再到并行型的演进历程。特别是2002年到2016年间，探针机的提出使得DNA计算取得了突破性的进展。探针机是一种底层全并行数学计算模型，它是在建立图着色DNA计算模型时被发现的，它的出现为计算机科学提供了一个与图灵机不同的新型数学计算模型，此模型也已受到不少学者乃至企业界人士的关注。
本书系统地总结了生物计算领域数十年来全球学者的主要研究成果，主要内容涵盖DNA计算的基础理论、关键技术、实验操作、计算模型以及在各领域的应用实例。本书共分12章。第1章～第4章详细介绍图与计算复杂性、生物计算数据[DNA、核糖核酸（Ribonucleic Acid，RNA）及蛋白质]、生物计算算子（酶与生化操作），以及电泳、聚合酶链反应（Polymerase Chain Reaction，PCR）等在DNA计算中发挥关键作用的技术和方法，为读者理解DNA计算的运作方式奠定基础。第5章重点阐述DNA编码理论与算法，帮助读者掌握实验设计和操作的要点。第6章～第8章深入探讨枚举型、非枚举型、并行型等多种DNA计算模型的构建思路和优缺点，为解决不同类型的计算问题提供多样化的模型选择。第9章与第10章精选一些DNA计算在密码学、生物信息学、优化问题等领域的应用案例，展示DNA计算的广阔应用前景。第11章与第12章介绍RNA计算与蛋白质计算的相关理论、应用。
本书的系统性、前沿性和实用性较强。系统性体现在对DNA计算领域的知识进行了全方位的梳理和整合，同时也对RNA计算与蛋白质计算做了较详细的介绍，从基础到应用，从理论到实践，构建起一个完整的知识体系。前沿性体现在紧跟当前DNA计算研究的最新进展，如对探针机、DNA自组装等前沿技术进行了深入剖析，能够帮助读者了解和掌握该领域的新动态。实用性则体现在对实验操作步骤的详细描述和对计算模型构建方法的清晰阐释等方面，能够为读者开展相关研究提供切实可行的指导。
在编写方法上，本书采用了理论与实践相结合的方式。首先，结合大量文献资料，对DNA计算的基础理论和关键技术进行了深入研究和系统总结。其次，结合我们在 DNA 计算实验研究中的实践经验，对实验操作步骤和注意事项进行了详细阐述。
本书适合图论与算法、生物信息学、计算机科学、分子生物学等领域的科研人员、高等学校师生以及对生物计算感兴趣的自学者阅读。对科研人员而言，本书可以作为开展 DNA 计算研究的参考书，帮助他们了解该领域的研究动态和技术进展，为他们的科研工作提供新的思路和方法。对高等学校的师生而言，本书适合作为生物计算相关课程的教材或参考书，可帮助学生系统学习DNA计算的基础知识和技能，为今后的学习和研究打下坚实的基础。对自学者而言，本书语言通俗易懂且实例丰富，可帮助他们快速入门并深入理解 DNA计算的精髓。
在阅读本书时，读者须注意以下几点。首先，由于 DNA 计算涉及多学科知识的交叉融合，读者应具备一定的生物学、计算机科学和图论基础，以便更好地理解和掌握书中的内容。其次，本书中的实验操作步骤和计算模型构建方法需要在实践中不断摸索和验证，因此建议读者在阅读时与实际操作相结合，以加深理解和提高应用能力。此外，由于 DNA 计算领域的研究日新月异，读者在阅读过程中应保持开放的心态，积极关注最新的研究进展和技术动态，以便及时更新自己的知识储备。
本书的编写得到了朱恩强、强小利、方刚、寇铮、石晓龙、刘文斌、王燕、陈智华、邵泽辉、张凤月、张凯和陈从周等的大力支持与帮助。本书内容（特别是插图）进行了1年多的持续修改与打磨，凝聚着他们每个人的汗水，在此向他们表示深深的感谢！刘婵娟、刘小青、冷煌等对本书进行了详细校对，在此也向他们表示感谢。最后，感谢人民邮电出版社，感谢贺瑞君等编辑的大力支持，本书得以顺利出版。
由于时间仓促，书中难免存在不足，敬请广大读者批评指正。
衷心希望本书能够为读者提供有价值的知识和启发，推动DNA计算领域的研究和应用不断发展。同时，我也期待与广大读者、同行进行深入交流和探讨，共同为生物计算事业的进步贡献力量。
许进
2025年2月7日于北京
生物计算是指以生物大分子作为信息处理数据的计算。生物大分子主要包括DNA、RNA和蛋白质，故生物计算可相应地分为DNA计算、RNA计算和蛋白质计算。截至本书成稿之日，限于生化操作技术水平，生物计算的研究主要集中于DNA计算。本书重点介绍DNA计算，对RNA计算与蛋白质计算也给予一定的介绍。本章介绍生物计算的产生、计算机的一般定义与计算模型、生物计算的研究意义与进展。
人类社会文明与信息处理的计算工具息息相关。计算工具是衡量人类社会文明程度的重要依据，也是推动人类社会发展的主要动力。人类社会历经石器时代、铁器时代、蒸汽时代、电气时代、信息时代，当前正处于人工智能时代，计算工具也由简单到复杂、由低级到高级，历经结绳记事、算筹、算盘、机械计算机、电子计算机等。其中，电子计算机也从电子管计算机、晶体管计算机、个人计算机（Personal Computer，PC）发展到当今的超级计算机，它们在不同的历史时期为人类社会的发展做出了不可磨灭的贡献。图1.1所示为人类计算工具发展历程。
图1.1 人类计算工具发展历程
其实，以人类神经系统为代表的生物神经系统一直都是人类社会信息处理的最好工具，该工具也随时代的变迁不断进化，进化的结果是脑神经系统愈发复杂。图 1.2 所示为人类神经系统的进化过程示意。人脑这个信息处理系统，不仅自身在进化发展，而且人类其他信息处理工具均由它设计研发，其中电子计算机是当今广泛应用的先进人造计算工具。
图1.2 人类神经系统的进化过程示意
电子计算机是当今人类社会信息处理的核心工具，人们的生活离不开它。但是，电子计算机的计算模型是图灵机，图灵机是串行计算模式，故电子计算机不能有效求解NP完全问题。NP完全问题的特点是所需计算量随问题规模的增大呈指数级增长。而电子计算机的工艺制造技术已达极限，这迫使人们开始寻求新的计算模型，以期通过创造新的计算工具来解决阻碍当今社会发展的NP完全问题。
在寻求新计算模型的过程中，科学家从多个领域展开探索，相继提出了模拟脑信息处理的人工神经网络、模拟遗传机理的进化计算、基于生物大分子特性的生物计算、基于量子特征的量子计算、基于光特性的光计算等。当对这些计算模型研究到一定程度时，相应的计算机就会被研发出来。因此，可形象地称当今非传统计算机的研究处于“战国时期”，生物计算是“战国”中的“一员”。
由于生物计算主要用于求解NP完全问题，故本书第2章会较详细地介绍图论基础、图灵机、可计算性，以及基于图灵机的计算复杂性理论等。
生物计算源自理查德·菲利普斯·费曼（Richard Phillips Feynman）在1961年提出的研制亚微尺度计算机的构想[1]。1973年，查尔斯·H.贝内特（Charles H. Bennett）提出了一种用酶来催化的图灵机[2]；20世纪80年代，以蛋白质为信息处理数据的二态分子计算模型被提出，称为蛋白质计算模型。蛋白质计算模型实际上是受电子计算机的影响，希望用分子产生可控的“二态”来模拟所谓的“0,1”目标。关于蛋白质计算的具体内容将在第12章介绍。
1994年，伦纳德·阿德曼（Leonard Adleman）建立了一种枚举DNA计算模型，用于求解7个顶点有向图的哈密顿路径（Hamilton Path）问题，该模型的基本原理是以DNA分子为“数据”，以生物酶与聚合酶链反应（Polymerase Chain Reaction，PCR）等为“算子”，获得问题的解[3]，详述见第6章。DNA计算模型产生的另一个重要背景是人类基因测序计划这项巨大工程的实施。人类基因测序计划促使基因工程、分子生物学理论、生化操作技术（尤其是DNA测序技术）快速发展，为DNA计算的产生、实现与发展提供了丰沃的“土壤”，也为DNA计算机的研发奠定了基础。
作者在此领域的一些早期综述文章见文献[4-8]，感兴趣的读者可自行查阅。在DNA计算的研究过程中，作者发现了一种全并行计算模型——探针机[9]，相关理论及应用将在第9章给出。
电子计算机的定义显然不适用于计算机的一般定义，本节介绍计算机的一种形式化定义，并在此基础上给出计算机的分类。
简言之，计算机就是基于具有一定通用性的计算模型，用适应该计算模型的材料研制的机器。或者说，计算机是基于某类材料建立与之相匹配的计算模型，并以此为基础研制的机器。在选定材料与计算模型后，还需为计算机设计一种系统结构，也称体系结构（Architecture）。基于此，给出计算机的一种形式化定义：
计算机=计算模型+实现材料+体系结构
例如，电子计算机的计算模型是图灵机，实现材料是电子元器件（如二极管、三极管、电阻器、电容器等），体系结构为冯·诺依曼体系结构（von Neumann Architecture）。该体系结构由 5 个部分构成：运算器（完成各种算术运算、逻辑运算和数据传送等数据处理工作）、控制器（控制程序的执行）、存储器（存储程序和数据）、输入设备（将数据或程序输入计算机中，如鼠标、键盘等），以及输出设备（将数据或程序的处理结果展示给用户，如显示器、打印机等）。其中，运算器和控制器组成计算机的中央处理器（Central Processing Unit，CPU）。这五大基本组成部件通过指令进行控制，并在不同部件之间进行数据传递。
电子计算机是冯·诺依曼设计的，但当今计算机领域内的最高奖被命名为“图灵奖”，而非“冯·诺依曼奖”。计算模型在计算机中的重要性由此可见一斑。
当前，计算机及计算模型通常是以实现材料或实现材料的尺度来命名的。例如，电子计算机、生物计算机（包括DNA计算机、RNA计算机、蛋白质计算机）是以实现材料命名的，量子计算机则是以实现材料的尺度命名的。而计算机的核心是计算模型，因此，上述计算机的命名似乎不够贴切。遗憾的是，截至本书成稿之日，上述计算机无论是可实用化的，还是在实验室里的，采用的计算模型均为图灵机。从这个角度来讲，基于实现材料或实现材料的尺度命名计算机是合理的。
计算机的计算模型可分为以下4类。
（1）串行计算模型。图灵机就是标准的串行计算模型，其实，早期的机械计算机的计算模型均为串行计算模型。
（2）全并行计算模型。本书第 9 章介绍的探针机就是一种全并行计算模型。此计算模型的一个基本特征是数据维数≥2，一般为三维。
（3）串/并计算模型。人脑信息处理的数学模型就是串/并计算模型。人脑有5个并行的感觉系统，而每个感觉系统在信息处理过程中是串行的，这似乎反映出串/并计算模型的智能化程度。
（4）智能计算模型。采用智能计算模型的计算机称为智能计算机。关于智能计算机，本书不予讨论，这里仅给出其形式化定义：
智能计算机=智能计算模型+体系结构+实现材料+基本智能集
从 1994 年至今，DNA 计算的研究已有三十年的历史。这些年来，DNA计算主要用于求解NP完全问题、研发DNA计算机。另外，从DNA计算的研究过程中衍生出来的DNA分子自组装技术，促进了DNA纳米器件领域的研究，为用于肿瘤诊断与药物递呈的纳米机器人的研发提供了条件。
在生物计算研究领域内，DNA 计算异军突起的主要原因是：目前对DNA分子及相关生化技术的操控比RNA和蛋白质容易实现，且DNA计算具有如下四大优势[4-8]。
（1）并行性高。DNA计算中的“数据”是DNA分子，数据间的“运算”是双链 DNA（double-stranded DNA，dsDNA）的解链、单链DNA（single-stranded DNA，ssDNA）的连接和切割等基本运算，这些基本运算可并行处理。特别是DNA分子的海量性，使得DNA计算的并行性极高。
（2）信息存储量巨大。由于组成DNA分子的4个碱基（A、C、G、T，详见3.1.1小节）的平均长度仅为0.34nm，按每条DNA序列有1000bp[1]计算，长度也仅有340nm。可以粗略地估计，1m3DNA可存储1万亿亿个二进制数据，远超当前全球所有电子计算机的总存储量。
[1] 碱基对（base pair，bp）是核酸分子的双螺旋结构中，一条链上的碱基与另一条链上的碱基之间通过氢键形成的一种化学结构，常用作表征DNA或双链RNA长度的单位，如千碱基对（kbp）和兆碱基对（Mbp）。
（3）能耗极低。粗略估计，DNA计算求解一个问题所消耗的能量仅为一台电子计算机完成同样计算所消耗能量的十亿分之一。
（4）算子丰富。DNA计算中的算子众多，如dsDNA分子的解链运算、两个ssDNA之间的连接运算、将一个DNA分子切割成两个或多个的切割运算、DNA链的复制运算（聚合酶）等。此外，还包括已有生化仪器的运算，如PCR扩增运算等。
DNA计算的上述优势吸引了不同领域（如生物工程、计算机科学、数学、物理、化学、控制科学等）的许多研究人员开展相关研究。
DNA 计算的研究目标是研发出实用的 DNA 计算机。研究进展显示，DNA计算距实用化越来越近。例如，在搜索一个赋权图中两个顶点间的所有路径时，只需要将这两个顶点所代表的DNA链作为引物，实施一次PCR扩增运算，即可获得所有路径。又如，伦纳德·阿德曼（Leonard M. Adleman）组在2002年求解可满足性 （Satisfiability，SAT） 问题时，搜索次数是220次[10]。文献[11]建立了求解图顶点着色问题的DNA计算模型，给出了61个顶点3-着色的所有解，搜索次数已达359次，这是截至本书成稿之日生物计算中搜索规模最大的实例，此例也证明了DNA计算的巨大潜力。
NP完全问题有很多，但斯蒂芬·阿瑟·库克（Stephen Arthur Cook）在1971年证明了所有NP完全问题在多项式时间内均可相互归约（Cook凭此项证明于1982年获得图灵奖）。这就意味着，所有的NP完全问题均可转化为图着色这个典型的NP完全问题。而DNA计算在求解图着色问题的进展已凸显出它在求解NP完全问题上的优势，为求解NP完全问题提供了新思路。NP完全问题的每一点进步，都会给当今社会发展带来不可估量的贡献。例如，蛋白质结构预测、列车调度、航迹规划等NP完全问题有望取得突破，基础科学领域（特别是数学、运筹学与理论计算机科学）中的一些难题有望得到解决。
按模型特点的不同，DNA计算的研究可分如下4个方向。
（1）枚举型DNA计算模型（1994—2005年）。DNA计算处于起步阶段，许多工作处于探索期。该方向主要针对一些困难的NP完全问题，研究如何基于DNA分子的特性构建计算模型，怎样对DNA链进行编码；如何进行生化实验，如何实施解的检测[怎样把问题的解从生物化学反应（简称生化反应）池中找出来]等。因此，在这段时间，绝大多数研究人员误以为DNA计算可利用DNA分子的微小性，以空间换时间。枚举型DNA计算模型将在第6章介绍。
（2）非枚举型图顶点着色DNA计算模型（始于2006年）。很容易算出，若用枚举型DNA计算模型求解200个顶点的4-着色问题，所需的DNA分子质量比地球质量还大。因此，DNA计算必须走非枚举型之路。作者团队首先提出非枚举型DNA计算模型，相关研究将在第7章详细介绍。
（3）并行型图顶点着色DNA计算模型（简称并行DNA计算模型）（始于2007年）。在非枚举型DNA计算模型的基础上，作者团队于2007年提出并行DNA计算模型。该模型的创新点在于并行性：将一个给定的图划分为若干个子图，并求出每个子图的着色；在求解每个子图着色的过程中，给出一种并行PCR连续删除非可行解（简称非解）技术；最后，将所有子图解连接起来，采用类似删除子图的非可行解法，删除整图中其余非可行解。并行DNA计算模型将在第8章详细介绍。
（4）探针机（始于2002年）。在建立图顶点着色DNA计算模型时，作者团队发现了一种仅通过一次运算就可获得一个图的全部k-色图的方法，并由此提出了一种全并行的新型DNA计算模型——探针机。探针机相关研究及应用将在第9章简要介绍。
[1] FEYMAN R P. There’s plenty of room at the bottom[J]. NY: Minaturization, 1961. 282-296.
[2] BENNETT C H. On constructing a molecular computer[J]. IBM Journal of Research and Development, 1973, 17: 525-532.
[3] ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021-1024.
[4] 许进, 张雷. DNA 计算机原理，进展及难点 (Ⅰ)：生物计算系统及其在图论中的应用[J]. 计算机学报, 2003, 26(1): 1-11.
[5] 许进, 黄布毅. DNA 计算机：原理，进展及难点 (Ⅱ)：计算机“数据库”的形成——DNA 分子的合成问题[J]. 计算机学报, 2005, 28(10): 1583-1591.
[6] 许进, 张社民, 范月科, 等. DNA 计算机原理、进展及难点(Ⅲ)：分子生物计算中的数据结构与特性[J]. 计算机学报, 2007, 30(6), 869-880.
[7] 许进, 谭钢军, 范月科, 等. DNA 计算机：原理、进展及难点(Ⅳ)：论DNA计算模型[J]. 计算机学报, 2007, 30(6): 881-893.
[8] 许进，李菲. DNA计算机原理、进展及难点(Ⅴ)：DNA分子的固定技术[J]. 计算机学报, 2009, 2283-2299.
[9] XU J. Probe machine[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(7): 1405-1416.
[10] BRAICH R S, CHELYAPOV N, JOHNSON C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J]. Science, 2002, 296(5567): 499-502.
[11] XU J, QIANG X, ZHANG K, et al. A DNA computing model for the graph vertex coloring problem based on a probe graph[J]. Engineering, 2018, 4(1): 61-77.
