RNA 折叠结构预测算法与计算复杂性

　　《RNA 折叠结构预测算法与计算复杂性》介绍了RNA结构特征、假结表示模型和较小自由能量原理等内容。重点介绍了包含假结的RNA折叠结构预测启发式算法、限制性RNA结构预测问题的精确算法、多项式时间近似方案、近似算法等问题。分析其时间复杂度和空间复杂度，比较其特异性和敏感性。针对NP难问题，设计了预测包含假结的1+ε（ε>0）多项式时间近似方案，分析了包含假结的RNA折叠结构，剖析连续堆叠和假结的结构特性，提出求解较大堆叠数的近似算法。针对RNA折叠结构盆跳图的结构和性质进行解析，对几种类型加以分析、分类，并对类型之间的转换进行阐述。最后对RNA折叠结构的应用加以简单的介绍。

暂缺《RNA 折叠结构预测算法与计算复杂性》作者简介

目录
前言
第1章 绪论 1
1.1 背景 1
1.2 国内外研究现状 3
1.3 算法与复杂性 9
1.4 P类、NP类及NPC类问题 10
1.5 NP难问题及其近似算法 11
1.6 多项式时间近似方案 13
1.7 NPC命题的证明 13
1.8 本书主要工作 16
参考文献 16
第2章 RNA折叠结构与能量模型 19
2.1 RNA结构与碱基序列 19
2.2 RNA结构介绍 20
2.2.1 RNA二级结构 20
2.2.2 RNA三级结构 21
2.3 RNA二级结构预测方法 22
2.3.1 序列对比方法 24
2.3.2 亲缘分析法 24
2.3.3 热动力学最小自由能量方法 25
2.4 假结结构 26
2.5 自由能量模型 27
2.5.1 自由能量参数 27
2.5.2 最邻近邻居模型 28
参考文献 28
第3章 典型的RNA结构预测算法简介 33
3.1 引言 33
3.1.1 研究目标 33
3.1.2 拟解决的有关科学问题 34
3.2 MFOLD算法 34
3.3 最大基对数算法 36
3.4 包含假结的RNA折叠结构预测 37
3.5 Rivas算法与JR算法 37
3.5.1 Rivas算法 37
3.5.2 JR算法 39
3.6 Lyngso算法 39
3.7 优化组合算法 40
3.8 Abrahams算法 41
参考文献 42
第4章 包含假结的RNA折叠结构预测启发式算法 44
4.1 引言 44
4.2 RNA折叠结构分析 46
4.3 计算最大堆叠的RNA二级结构预测算法 47
4.3.1 算法设计 47
4.3.2 算法思想 48
4.3.3 算法分析 49
4.3.4 实验结果 50
4.3.5 实验对比分析 52
4.3.6 结论 53
4.4 启发式算法设计 53
4.5 算法复杂性分析 56
4.6 实验结果 57
参考文献 59
第5章 计算最大堆叠数的多项式时间近似方案 60
5.1 引言 60
5.2 RNA折叠结构中最大堆叠数问题的复杂性 63
5.3 计算最大堆叠数算法 64
5.4 基于茎区的计算最大堆叠数问题近似方案 64
参考文献 66
第6章 带假结的RNA折叠结构预测近似算法 67
6.1 引言 67
6.2 平面RNA二级结构的近似算法 69
6.3 一般RNA二级结构的近似算法 73
6.4 平面RNA结构中的NP完全性 75
6.4.1 RNA折叠结构序列构建 76
6.4.2 If-part的正确性 76
6.4.3 Only-ifpart的正确性 77
参考文献 81
第7章 基于BHG的RNA折叠结构预测算法 83
7.1 基本概念 83
7.2 基于BHG的RNA折叠结构预测方案 83
参考文献 88
第8章 RNA折叠结构与基因编辑技术 89
8.1 简介 89
8.2 技术原理 92
8.2.1 基因编辑是DNA断裂及修复机制的技术 92
8.2.2 重组核酸酶介导技术 93
8.3 技术应用 98
8.3.1 国际基因编辑技术进展 98
8.3.2 我国基因编辑技术进展 101
参考文献 102
第9章 总结与展望 106
9.1 总结 106
9.2 展望 106
基本术语表 108