DNA计算是借助于分子生物技术进行计算的新方法。凭借着极大的存储密度和高度并行性，DNA计算为求解NP完全问题等复杂组合优化问题提供了一条全新的途径，开创了广阔的应用前景。本书主要介绍DNA计算核酸编码原理及方法，具体包括DNA计算的研究进展和背景、DNA计算的生物化学基础、DNA编码问题及其复杂性分析、DNA二级结构预测和最小自由能模型、隐枚举核酸序列编码算法、DNA编码在图着色DNA计算中的应用。
样章试读
目录
- 第1章DNA计算的产生与发展1
1.1国内外研究进展5
1.2DNA计算问题难点15
1.3DNA计算编码方法的研究意义17
第2章DNA计算的生物化学基础19
2.1DNA的分子组成和结构19
2.2DNA计算生物化学操作23
2.2.1DNA的变性？复性和杂交23
2.2.2PCR扩增25
2.2.3凝胶电泳分离26
2.2.4DNA链的外切27
2.2.5DNA链的内切28
2.2.6DNA链的连接29
2.2.7特定DNA分子的提取31
2.2.8DNA序列的测定31
2.3DNA分子计算的实现途径32
2.3.1基于溶液反应的DNA分子计算32
2.3.2基于表面的DNA计算33
2.3.3基于DNA芯片的DNA计算33
第3章DNA编码问题及其复杂性研究35
3.1DNA编码研究的重要意义35
3.2DNA编码问题的复杂性分析37
3.3DNA编码约束及分析40
3.3.1基于汉明距离的编码约束40
3.3.2DNA二级结构约束44
3.3.3DNA化学特性约束45
3.3.4DNA子序列碱基组成约束47
3.4DNA序列设计算法47
3.5基于热力学和汉明距离编码方法的分析比较50
3.5.1限制非特异性杂交的完备性比较50
3.5.2汉明距离的编码方法计算量分析51
3.5.3基于热力学的编码约束分析53
3.5.4核酸编码方法比较56
第4章DNA二级结构预测和最小自由能模型57
4.1DNA二级结构模型57
4.2动态规划DNA二级结构预测算法60
4.3改进的动态规划回溯树搜索65
4.4近邻热力学模型和最小自由能71
4.4.1NearestGNeighbor热力学模型71
4.4.2WatsonGCrick堆栈结构及其热力学模型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.9DNA二级结构预测例子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.2DNA编码约束转换隐枚举评估函数113
6.2.1转换汉明距离约束115
6.2.2转换相似度约束116
6.2.3转换HGmeasure约束及3′端HGmeasure约束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隐枚举算法和模板G映射算法的编码比较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.2DNA编码设计在图着色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.2STG编号平面嵌入算法154
8.2.1STG编号算法154
8.2.2平面嵌入160
8.3DNA二级结构平面嵌入算法163
8.3.1布局算法166
参考文献170
后记174
京公网安备 11010102004214号