RNA二级结构预测的快速计算

摘要

RNA二级结构预测要求根据RNA序列计算序列中符号的配对集，使得配对集所形成的结构具有最小自由能量。如何得到更加准确的预测结构，是近三十年来生物信息学的热点之一。 以往人们采用序列比对分析法获得RNA序列的准确二级结构，但是该方法人工工作量大，条件限制较多，因此无法广泛应用。目前热动力学最小自由能量方法已成为：RNA二级结构预测的最常用方法。基于动态规划和最邻近能量模型的Mfold算法是计算RNA二级结构最小自由能量的经典方法。 假结是RNA中普遍存在的二级结构单元。但Mfold算法不能预测假结。目前预测假结的最好算法是Rivas算法。该算法能得到最优平面假结结构和部分非平面假结结构，但算法的时间复杂度太高。 本文首先实现和改进Mfold算法。基于环和最临近能量模型，使用实验室测量的能量数据，通过动态规划计算子链的最小自由能量，并且计算最优二级结构，实现Mfold算法。把同轴堆叠模型加入Mfold算法，从而得到具有更低的自由能量的RNA二级结构，实现Mfold算法的改进。改进算法的时间和空间复杂度与Mfold算法相同。 我们通过实验比较了Mfold算法和改进算法，结果表明，相比Mfold算法，改进算法的预测准确度由76.43％提高到78.25％。 然后本文实现了多折叠的次优算法。该算法首先把线性RNA序列抽象为环链，任意选择一个基对将环链划分成内段和外段，分别计算内段和外段的能量和结构。内段和外段的能量之和为次优能量，结构之组合为次优结构，其时间复杂度是O(n<'3>)，空间复杂度是O(n<'2>)。次优算法为RNA二级结构分析提供更多有用的信息。 随后本文给出了一个计算简单假结的二级结构算法。通过任意选择两个交叉的基对，把序列划分为五段，分别计算每一段的能量和结构，从而得到包含一个简单假结的二级结构。该算法的时间和空间复杂度与Mfold算法相同。 最后，本文给出30余个实际序列的实验测试，进行对比分析和准确度计算。 本文的主要创新点为： 1.引入同轴堆叠改进Mfold算法，将Mfold算法的预测准确度由76.43％提高到78.25％。 2.提出带人工干预的简单假结二级结构计算方法，其时间复杂度和空间复杂度分别为O(n<'3>)和O(n<'2>)。 3.用Java语言实现了Mfold算法和Mfold改进算法，用30多个例子比较了两种算法的优劣。

目录

文摘

英文文摘

声明

1绪论

2 RNA二级结构预测的能量模型

2.1环

2.2最临近能量模型

2.2.1一环

2.2.2二环

2.2.3多分枝环和外环

2.3假结简介

3 Mfold算法及其改进

3.1动态规划

3.2 Mfold算法

3.2.1数据结构

3.2.2算法

3.3 Mfold算法改进

3.4二级结构计算

4次优折叠

4.1原理

4.2次优二级结构计算

5简单假结二级结构计算方法

5.1简单假结算法

5.2算法改进

6算法实现与计算结果比较

6.1软件实现

6.1.1平台与开发原则

6.1.2文档结构与工具集

6.2最优结构计算举例

6.3次优结构计算举例

6.4简单假结结构计算举例

6.4.1改进前

6.4.2改进后

6.5比较分析

结束语

参考文献

致谢

攻读学位期间发表的学术论文