第1章 绪论 1
参考文献 5
第2章 理论计算机科学基础 6
2.1 图论 6
2.1.1 基本概念 6
2.1.2 通路与回路 8
2.1.3 闭包与路径 8
2.1.4 树 9
2.1.5 二部图 10
2.2 有限状态自动机 11
2.2.1 字符串和语言 11
2.2.2 确定型有限状态自动机 12
2.2.3 非确定型有限状态自动机 13
2.2.4 正则表达式 14
2.2.5 随机型有限状态自动机 15
2.3 可计算性 17
2.3.1 图灵机 17
2.3.2 通用图灵机 18
2.3.3 Church论题 19
2.3.4 寄存器机 21
2.3.5 细胞自动机 21
2.4 形式语言 23
2.4.1 文法与语言 23
2.4.2 乔姆斯基体系 23
2.4.3 文法与自动机 24
2.4.4 不可判定性 25
2.5 组合逻辑 28
2.5.1 布尔电路 28
2.5.2 复合电路 29
2.5.3 最小项和最大项 30
2.5.4 典型电路 31
2.5.5 加法器电路 32
2.6 计算复杂性 33
2.6.1 时间复杂性 33
2.6.2 无穷渐近 34
2.6.3 判定问题 35
2.6.4 组合优化问题 37
参考文献 38
第3章 分子生物学基础 39
3.1 DNA 39
3.1.1 分子结构 39
3.1.2 DNA操作技术 41
3.2 理化性质 43
3.2.1 热力学性质 43
3.2.2 化学动力学 45
3.2.3 DNA退火动力学 46
3.2.4 链置换动力学 47
3.2.5 随机型化学动力学 47
3.3 基因 52
3.3.1 结构与生物合成 52
3.3.2 DNA重组 54
3.3.3 基因组 55
3.4 基因表达 55
3.4.1 蛋白质的生物合成 55
3.4.2 蛋白质的分子结构 58
3.4.3 酶 60
3.5 细胞与生物体 63
3.5.1 真核细胞与原核细胞 63
3.6 病毒 64
3.6.1 一般结构和分类 64
3.6.2 应用 65
参考文献 66
第4章 DNA计算中的编码问题 68
4.1 约束条件 68
4.1.1 自由能和解链温度 68
4.1.2 距离 69
4.1.3 相似度 69
4.2 DNA语言 71
4.2.1 无关语言 71
4.2.2 杂交属性 73
4.2.3 小DNA语言 74
4.3 DNA编码的构造及其规模的界 75
4.3.1 反码和反补码 75
4.3.2 GC-含量恒定码 77
4.3.3 相似码 79
4.4 试管中的随机选择机制 81
4.4.1 通用选择模型 82
4.4.2 选择性编码设计 83
4.5 本章小结 83
参考文献 83
第5章 非自治DNA计算模型 85
5.1 开创性工作 85
5.1.1 Adleman的首次实验 85
5.1.2 Lipton的首篇论文 87
5.2 过滤模型 88
5.2.1 无记忆过滤模型 88
5.2.2 记忆过滤模型 89
5.2.3 标记-破坏过滤模型 89
5.2.4 分管-合管过滤模型 91
5.2.5 阻塞过滤模型 93
5.2.6 表面过滤模型 93
5.3 粘贴系统 96
5.3.1 粘贴机 96
5.3.2 组合链库 97
5.3.3 有用的子程序 98
5.3.4 NP完全问题 105
5.4 剪接系统 120
5.4.1 基本剪接系统 120
5.4.2 递归可枚举剪接系统 122
5.4.3 通用剪接系统 123
5.4.4 重组系统 124
5.5 本章小结 126
参考文献 126
第6章 自治DNA计算模型 128
6.1 算法自组装 128
6.1.1 自组装 128
6.1.2 DNA图 129
6.1.3 线性自组装 130
6.1.4 瓦片组装 132
6.2 有限状态自动机模型 137
6.2.1 两状态两字符自动机 137
6.2.2 长度-编码型自动机 140
6.2.3 粘贴自动机 142
6.2.4 随机型自动机 146
6.3 DNA发夹模型 146
6.3.1 Whiplash PCR 146
6.3.2 可满足性问题 149
6.3.3 汉密尔顿路径问题 150
6.3.4 最大团问题 153
6.3.5 发夹结构 156
6.4 计算模型 157
6.4.1 神经网络 157
6.4.2 Tic-Tac-Toe网络 159
6.4.3 逻辑电路 163
6.4.4 图灵机模型 165
6.5 本章小结 168
参考文献 168
第7章 细胞内DNA计算 171
7.1 纤毛虫计算 171
7.1.1 纤毛虫 171
7.1.2 基因组装模型 173
7.1.3 分子内作用的字符串模型 174
7.1.4 分子内作用的图模型 176
7.1.5 分子间作用的字符串模型 178
7.2 生物分子计算 180
7.2.1 基因治疗 180
7.2.2 反义技术 181
7.3 基于细胞的有限状态自动机模型 182
7.4 反义有限状态自动机模型 185
7.4.1 基本模型 185
7.4.2 诊断规则 185
7.4.3 诊断与治疗 186
7.5 可计算基因模型 187
7.5.1 基本模型 188
7.5.2 诊断规则 189
7.5.3 诊断与治疗 190
7.6 本章小结 191
参考文献 192