第1章 DNA计算的产生与发展 1
1.1 国内外研究进展 5
1.2 DNA计算问题难点 15
1.3 DNA计算编码方法的研究意义 17
第2章 DNA计算的生物化学基础 19
2.1 DNA的分子组成和结构 19
2.2 DNA计算生物化学操作 23
2.2.1 DNA的变性、复性和杂交 23
2.2.2 PCR扩增 25
2.2.3 凝胶电泳分离 26
2.2.4 DNA链的外切 27
2.2.5 DNA链的内切 28
2.2.6 DNA链的连接 29
2.2.7 特定DNA分子的提取 31
2.2.8 DNA序列的测定 31
2.3 DNA分子计算的实现途径 32
2.3.1 基于溶液反应的DNA分子计算 32
2.3.2 基于表面的DNA计算 33
2.3.3 基于DNA芯片的DNA计算 33
第3章 DNA编码问题及其复杂性研究 35
3.1 DNA编码研究的重要意义 35
3.2 DNA编码问题的复杂性分析 37
3.3 DNA编码约束及分析 40
3.3.1 基于汉明距离的编码约束 40
3.3.2 DNA二级结构约束 44
3.3.3 DNA化学特性约束 45
3.3.4 DNA子序列碱基组成约束 47
3.4 DNA序列设计算法 47
3.5 基于热力学和汉明距离编码方法的分析比较 50
3.5.1 限制非特异性杂交的完备性比较 50
3.5.2 汉明距离的编码方法计算量分析 51
3.5.3 基于热力学的编码约束分析 53
3.5.4 核酸编码方法比较 56
第4章 DNA二级结构预测和最小自由能模型 57
4.1 DNA二级结构模型 57
4.2 动态规划DNA二级结构预测算法 60
4.3 改进的动态规划回溯树搜索 65
4.4 近邻热力学模型和最小自由能 71
4.4.1 Nearest-Neighbor热力学模型 71
4.4.2 Watson-Crick堆栈结构及其热力学模型 72
4.4.3 内单核苷酸错配结构及其热力学模型 74
4.4.4 内环结构及其热力学模型 75
4.4.5 凸环结构及其热力学模型 77
4.4.6 发卡结构及其热力学模型 78
4.4.7 悬挂末端结构及其热力学模型 79
4.4.8 多分支环和外环 80
4.4.9 DNA二级结构预测例子 81
第5章 基于遗传算法的DNA平面伪结的预测算法 86
5.1 遗传算法概述 87
5.2 遗传算法的原理与方法 88
5.2.1 产生初始种群 88
5.2.2 根据目标问题构造适应度函数 88
5.2.3 选择适应度高的个体进行杂交和变异 88
5.2.4 若干次迭代后最高适应度值的为最优解 91
5.3 遗传算法和传统搜索算法的比较 92
5.3.1 梯度下降法 92
5.3.2 模拟退火算法 93
5.3.3 遗传算法 94
5.4 遗传算法预测含平面伪结的DNA二级结构 98
5.4.1 适应度函数 99
5.4.2 选择运算 101
5.4.3 交叉运算 101
5.4.4 变异运算 103
5.4.5 算法流程图 104
5.4.6 算法比较与分析 105
第6章 隐枚举核酸序列编码算法 108
6.1 隐枚举核酸序列设计算法 109
6.1.1 生成所有的DNA序列n元组 110
6.1.2 算法思路及步骤 111
6.2 DNA编码约束转换隐枚举评估函数 113
6.2.1 转换汉明距离约束 115
6.2.2 转换相似度约束 116
6.2.3 转换H-measure约束及3′端H-measure约束 117
6.2.4 转换反补汉明距离约束 119
6.2.5 转换自补汉明距离约束 120
6.2.6 转换单链二级结构约束 121
6.2.7 转换连续性约束 122
6.2.8 转换GC含量约束 124
6.2.9 转换解链温度约束 125
6.2.10 转换最小自由能约束 126
6.2.11 转换限定子序列约束和重叠子序列约束 127
6.2.12 转换模版序列约束 128
6.2.13 多约束的隐枚举评估函数 129
6.3 算法收敛性分析 130
6.4 同其他编码算法的比较 130
6.4.1 隐枚举算法和模板-映射算法的编码比较 130
6.4.2 隐枚举算法和模拟退火算法的编码比较 133
6.4.3 隐枚举算法和遗传算法的编码比较 134
6.4.4 隐枚举算法和最小子串算法的编码比较 135
6.4.5 隐枚举算法和多目标进化算法的编码比较 137
6.4.6 隐枚举算法和动态规划算法的编码比较 138
第7章 DNA编码在图着色DNA计算中的应用 142
7.1 图顶点着色DNA计算算法 143
7.2 DNA编码设计在图着色DNA计算中的应用 145
第8章 DNA二级结构的平面嵌入算法 150
8.1 图 150
8.1.1 有向图 151
8.1.2 可平面图 151
8.1.3 顶点的度和图的度 152
8.1.4 连通图 153
8.2 ST-编号平面嵌入算法 154
8.2.1 ST-编号算法 154
8.2.2 平面嵌入 160
8.3 DNA二级结构平面嵌入算法 163
8.3.1 布局算法 166
参考文献 170
后记 174