目录 1
前言…………………………………………………………………………i第一章 绪论 1
1.1 DNA计算产生的背景 1
1.2 DNA计算的基本思想 3
1.3 DNA计算的研究现状 3
1.4 本书的内容及创新之处 9
1.4.1 本书研究的基本问题 9
1.4.2 本书的主要结果与创新之处 10
第二章 生物操作的基本概念 12
2.1 DNA的结构 12
2.2 DNA分子的操作 16
2.2.1 DNA链的分离和结合 16
2.2.2 DNA链的延伸 17
2.2.3 DNA链的外切 18
2.2.4 DNA链的内切 19
2.2.5 DNA链的连接 20
2.2.6 DNA链长度的测量 21
2.2.7 特定DNA分子的提取 21
2.2.8 DNA分子的复制 22
2.2.9 DNA序列的测定 22
2.2.10 微量点样技术 23
第三章 图与组合优化问题的DNA计算模型 24
3.1 引言 24
3.2 DNA计算 26
3.2.1 Hamilton路问题 26
3.2.2 可满足性（SAT）问题 28
3.2.3 最大团问题 34
3.2.4 最大独立集问题 37
3.2.5 其他问题 39
3.3 复杂性讨论 39
第四章 最小支撑树的DNA算法 41
4.1 最小支撑树问题 41
4.2 最小支撑树问题的算法设计 41
4.3 最小支撑树问题的DNA计算模型系统 43
4.3.1 最小支撑树问题的DNA编码 43
4.3.2 最小支撑树问题的生物操作 43
4.4 实例分析 44
4.5 结论分析 46
第五章 工序问题的DNA计算模型 47
5.1 引言 47
5.2.2 生物算法 48
5.2 工序问题的算法设计 48
5.2.1 基本算法 48
5.3 工序问题的编码和生物操作 49
5.3.1 编码 49
5.3.2 生物操作 49
5.4 实例分析 50
5.5 结论分析 55
第六章 中国邮递员问题的DNA计算模型 57
6.1 引言 57
6.2 DNA编码的基本原则 58
6.2.1 DNA编码的规范几何结构 58
6.2.2 有关记号和数学模型 60
6.2.3 限制在DNA编码上的对合关系 62
6.3 算法设计 63
6.2.4 规范几何结构的数学模型 63
6.3.1 基本算法 64
6.3.2 DNA算法 64
6.4 编码和生物操作 65
6.4.1 编码 65
6.4.2 生物操作 67
6.5 实例分析 68
6.6 结论分析 72
第七章 基于分子信标的DNA计算模型 74
7.1 引言 74
7.2 分子信标的研究进展 75
7.2.1 分子信标的结构性质和作用机制 75
7.2.2 分子信标的应用 76
7.3 分子信标与DNA计算 79
7.4.1 基本算法 80
7.4 基于分子信标的算法设计 80
7.4.2 生物算法 81
7.5 分子信标的编码和操作 81
7.5.1 编码 81
7.5.2 生物操作 82
7.6 实例分析 83
7.7 结论分析 85
7.8 注记 86
第八章 简单的0-1规划问题的DNA计算模型 87
8.1 引言 87
8.2 简单0-1规划问题的算法设计 88
8.2.1 基本算法 88
8.2.2 生物算法 88
8.3.2 生物操作 89
8.3 简单0-1规划问题的编码和生物操作 89
8.3.1 编码 89
8.4 实例分析 90
8.4.1 简单0-1规划问题的实例分析 90
8.4.2 案例分析中的DNA计算模型 93
8.5 生物操作的改进 95
8.6 结论分析 98
第九章 0-1规划问题表面DNA计算模型 99
9.1 引言 99
9.2 0-1规划问题的表面算法设计 100
9.2.1 基本算法 100
9.2.2 生物算法 101
9.3 0-1规划问题的编码和生物操作 101
9.3.1 编码 101
9.4 实例分析 102
9.3.2 生物操作 102
9.5 结论分析 106
9.6 注记 106
第十章 DNA计算的完备性与通用性 108
10.1 引言 108
10.2 DNA分子结构与形式语言 109
10.3 DNA计算的通用性 111
10.4 DNA计算的完备性 113
10.5 DNA计算的复杂度 114
第十一章 结论与展望 116
11.1 全书的结论 116
11.2 进一步研究方向 117
参考文献 120