生物计算是一种以DNA、RNA和蛋白质等生物大分子为数据的计算。本书较为深入地探讨DNA计算的各个方面，从基础理论到实验操作，再到解的检测，都囊括其中。同时，书中对RNA计算和蛋白质计算也进行了概述。全书共12章。其中，第1章～第4章详细介绍图与计算复杂性、生物计算数据、生物计算算子（酶与生化操作），以及在DNA计算中发挥关键作用的技术和方法。第5章重点阐述DNA编码理论与算法。第6章～第8章深入探讨枚举型、非枚举型、并行型等多种DNA计算模型的构建思路和优缺点。第9章与第10章介绍一些DNA计算在密码学、生物信息学、优化问题等领域的应用案例。第11章与第12章介绍RNA计算与蛋白质计算的相关理论与应用。这样的结构安排旨在为读者提供一个全面、系统的生物计算知识框架。
本书适合图论与算法、分子生物学、计算机科学、生物信息学及人工智能等领域的科研人员、高等学校师生，以及对生物计算感兴趣的读者阅读。

1.领域前沿：本书全面介绍了生物计算的三大领域DNA计算、RNA计算和蛋白质计算，涵盖了从基础理论到实验操作的全方位内容，为读者提供了一个系统的学习框架。
2.作者知名：由领域内知名学者著述，整合了多年的研究成果和最新发现，确保了书籍内容的权威性和实用性。
3.理论性与实用性兼备：不仅深入探讨了生物计算的理论基础，还详细介绍了实验操作和计算模型，使读者能够将理论知识应用于实际问题解决中。
4.案例分析丰富：书中提供了大量的实际案例分析，如DNA计算在求解NP完全问题上的应用，增强了内容的可读性和实用性，使读者能够更好地理解和掌握生物计算技术。
5.跨学科视角：本书融合了计算机科学、生物学、化学等多个学科的知识，为跨学科研究者提供了一个共同的交流平台，具有广泛的吸引力。

许进，北京大学教授，博士生导师。理学、工学双博士，专注于组合优化问题的研究。1996年，在国内率先开展生物计算研究。提出求解图着色的非枚举型、并行型等DNA计算新方法，使生物计算搜索规模达359，实现迄今国际上最大规模的生物计算实验。出版学术专著7部、译著1部，发表学术论文300余篇。作为第一完成人，获国家自然科学二等奖1项、自然科学一等奖2项、湖北省自然科学一等奖1项。先后主持国家自然科学基金重点、重大国际合作、专项基金、重大仪器专项、863、国家重大工程、国家重点研发计划共超十项。担任中国电子学会电路与系统分会副主任委员、中国通信学会云计算与大数据委员会副主任委员、中国网络空间安全协会理事；Artificial Intelligence Review与《电子与信息学报》副主编。曾任军委科技委领域专家、电子学会图论与系统优化专委会理事长、湖北省运筹学会理事长、北京市运筹学会副理事长、网络空间安全教咨委委员；第一、二、四、五、七、八届国际生物计算机大会主席。

第 1 章 绪论 1
11 生物计算的产生 1
12 计算机的一般定义与计算模型 3
13 生物计算的研究意义与进展 5
参考文献 7
第 2 章 图与计算复杂性 9
21 图论基础 9
211 图的定义与类型 9
212 图的度序列 15
213 图的运算 16
214 图的同构 20
215 图的矩阵 22
216 图着色 24
22 图灵机 30
221 图灵机的起源 30
222 图灵机的原理、类型及图灵等价性 32
23 可计算性 35
24 计算复杂性 36
241 P 问题与NP 问题 36
242 coNP 问题 42
参考文献 43
第3 章 生物计算数据：DNA、RNA 与蛋白质 47
31 DNA 分子 47
311 脱氧核苷酸 48
312 DNA 分子结构 51
313 DNA 分子类型 53
314 DNA 分子特性 59
315 DNA 生化反应 63
32 RNA 分子 65
321 RNA 分子的核苷酸 66
322 RNA 分子的结构 68
323 RNA 分子的类型 69
33 蛋白质分子 71
331 蛋白质的结构 71
332 蛋白质的类型 73
333 蛋白质计算输出检测技术 74
参考文献 75
第4 章 生物计算算子：酶与生化操作 78
41 生物计算常用工具酶 78
411 限制性内切核酸酶 78
412 DNA 聚合酶 81
413 DNA 连接酶 85
414 DNA 修饰酶 87
415 核酸酶 87
42 生物计算的生化操作 88
421 DNA 分子的合成 88
422 DNA 分子的切割、连接及粘贴 89
423 DNA 重组技术 92
424 变性与杂交 92
425 DNA 分子的扩增 92
426 DNA 分子的分离与提取 93
427 DNA 分子的检测与读取 95
428 可用于生物计算的经典生化操作技术 96
429 可用于生物计算的新型生化操作技术 98
4210 生物计算涉及的新型仪器 103
43 生物计算的关键技术：电泳 111
431 基本原理 111
432 凝胶电泳 112
433 免疫电泳 113
434 毛细管电泳 114
435 介电电泳 115
436 等速电泳 117
44 生物计算的关键技术：聚合酶链反应 117
441 PCR 发明之旅 118
442 基本原理 119
参考文献 124
第5 章 DNA 编码理论与算法 132
51 DNA 编码的背景与发展 132
52 DNA 编码问题 136
521 DNA 编码的常见约束 137
522 编码问题及其数学模型 143
523 当前DNA 编码算法分类 144
53 基于GC 含量的DNA 编码计数理论 146
531 DNA 编码计数理论 147
532 GC 含量相等的DNA 编码设计 150
54 模板编码理论与算法 151
541 模板编码理论 151
542 模板编码的搜索算法 153
543 编码的热力学稳定性 154
544 模板集的优化 155
55 进化多目标优化DNA 编码理论与算法 156
551 进化多目标优化DNA 编码理论 157
552 基于进化多目标优化的DNA 编码算法框架 159
56 隐枚举编码理论与算法 160
561 隐枚举编码理论 161
562 隐枚举算法的应用 162
参考文献 165
举型DNA 计算模型 173
61 有向哈密顿路径问题的DNA 计算模型 173
62 可满足性问题的DNA 计算模型 176
63 图的最大团与最大独立集问题的DNA 计算模型 181
64 0-1 规划问题的DNA 计算模型 184
65 图顶点着色问题的DNA 计算模型 186

参考文献 190
第7 章 非枚举型图顶点着色DNA 计算模型 194
71 基本思想 194
72 生物实现 195
721 生物操作步骤 195
722 实例分析与相关生化实验 196
73 计算模型分析 207
74 其他非枚举型DNA 计算模型 208
参考文献 210
第8 章 并行型图顶点着色DNA 计算模型 212
81 模型与算法 212
811 子图划分与桥点的确定 213
812 子图顶点排序与子图中每个顶点颜色集的确定 216
813 DNA 序列的编码 218
814 根据探针图确定探针 219
815 初始解空间的合成 221
816 非解删除 221
817 子图逐级合并与非解删除 222
818 解的检测 222
82 具体算例 223
821 子图划分与颜色集确定 223
822 编码 223
823 构建初始解空间 223
824 子图删除非解 224
825 子图合并与非解删除 227
83 复杂性分析 230
831 降低初始解空间的复杂性 230
832 提高并行性 232
参考文献 236
第9 章 探针机 237
91 探针机的产生背景 237
92 探针机的原理 239
921 图灵机机理分析 239
922 探针机的数学模型 240
93 探针机求解哈密顿问题 251
94 连接型探针机的一种实现技术 254
95 传递型探针机与生物神经网络 258
96 探针机功能分析 259
961 图灵机是探针机的一种特殊情况 260
962 图灵机能否模拟探针机 261
963 探针机的优势 261
参考文献 262
第 10 章 DNA 算法自组装 265
101 DNA Tile 计算 265
1011 DNA Tile 类型 266
1012 DNA Tile 计算实例 269
102 图灵等价的DNA Tile 计算 274
1021 DNA Tile 计算的数学模型 274
1022 DNA Tile 计算的图灵等价性 277
103 可编程DNA Tile 结构 280
104 单链DNA Tile 计算 281
105 基于SST 的通用DNA 计算 288
1051 基于SST 的迭代布尔电路计算模型 288
1052 基于可重复SST 的填充计算模型 292
106 DNA Origami 计算 294
1061 DNA Origami 技术 294
1062 DNA Origami 的可编程自组装 296
1063 DNA Origami 表面计算 298
1064 可计算DNA Origami 结构 299
参考文献 301
第 11 章 RNA 计算 305
111 RNA 分子的计算特性 305
112 解决NP 问题的RNA 计算模型 306
113 RNA 计算在逻辑门与逻辑电路方面的相关研究 308
1131 RNA 分子结构预测与设计 309
1132 基于分子自动机的RNA 计算 310
1133 结合RNA 干扰技术的RNA 计算 312
1134 结合核酶与适配体技术的RNA 计算 314
1135 结合CRISPR/Cas 基因编辑技术的RNA 计算 315
1136 与合成生物学技术结合的RNA 计算 317
参考文献 319
第 12 章 蛋白质计算 325
121 基于蛋白质构建逻辑运算器 325
1211 酶介导的逻辑运算器 326
1212 非酶介导的逻辑运算器 336
1213 基于人工设计的蛋白质的逻辑运算器 339
122 基于蛋白质构建算术运算器 340
123 基于蛋白质分子解决NP 完全问题 342
124 蛋白质存储 343
1241 基于细菌视紫红质的蛋白质存储 343
1242 蛋白质基忆阻器 345
参考文献 350