预测RNA二级结构的快速计算方法的研究

摘要

DNA是遗传信息的载体,遗传信息的作用通常由蛋白质的功能来表现,但DNA并非蛋白质合成的直接模板,合成蛋白质的模板是RNA。RNA二级结构预测问题是计算机科学和生物信息学的基本课题之一,RNA二级结构预测用于蛋白质功能分析,序列对比分析法及热动力学最小自由能量方法是RNA二级结构预测的两种基本方法,序列对比分析法的基本思想,是找出检测序列和目标序列的相似性。序列对比的最终实现,必须依赖于某个数学模型,在序列非常相近或新的独立序列的情况下,序列对比法不适应。目前热动力学最小自由能量方法已成为RNA二级结构预测的最常用方法。 目前预测RNA二级结构的大多数算法仅预测嵌套的RNA二级结构,不允许伪结点存在。但伪结点在几种已知RNA中具有重要功能。如Pleij等人于1985年预测了RnaSe P RNAS中的伪结点结构,并由Kock等人于1998年予以证实。 包含伪结点的RNA二级结构预测问题是NPC问题。目前预测包含伪结点的RNA二级结构的动态规划算法有：Rivals算法、B.Lyngsφ算法和Jens Reeder的代数动态规划等算法。Rivals算法、B.Lyngsφ算法都可预测包含伪结点的RNA二级结构.Rivas算法可计算包含任意平面伪结点和特定条件下的非平面伪结点结构,其时间复杂度为O(n~6),空间复杂度为O(n~4)。Lyngsφ算法仅可计算包含一个平面伪结点的结构,其时间复杂度为O(n~5),空间复杂度为O(n~3)。最近较好的预测算法使用其O(n~4)时间和O(n~3)的空间预测任意的平面伪结点。 动态规划算法需要的时间和空间较大,预测长度大于1000个碱基的RNA二级结构十分困难。嵌套的二级结构算法又不能预测伪结点结构,因此迫切需要快速算法预测包含伪结点的RNA二级结构。 本文提出一个预测RNA二级结构的贪心算法,算法思想为计算具有最多堆迭的RNA二级结构,该想法来源于“堆迭结构相对稳定”的

目录

摘要

ABSTRACT

第一章 绪论

1.1 研究背景

1.2 RNA二级结构预测的研究方法

2.1 序列对比方法

2.2 以亲缘分析法预测 RNA结构的原理

1.3 热动力学最小自由能量方法

1.4 研究结果

第二章 RNA二级结构预测中 NPC问题的判定

2.1 基本术语

2.2 自由能量参数

2.3 自由能量的表示

2.4 NPC问题的判定

2.4.1 NPC命题的证明

第三章 最小化自由能量方法的预测依据

3.1 基本结构

3.2 最小化自由能量预测

3.3 自由能量最小化方法

第四章 RNA二级结构预测算法

4.1 Mfold算法

4.1.1 模型与图解表示

4.1.2 动态规划

4.1.3 Mfold算法改进

4.2 Abrahams算法

4.3 Rivals算法

4.3.1 模型

4.3.2 动态规划

4.4 Lyngs算法

第五章 最大堆叠的 RNA二级结构快速预测算法

5.1 算法设计

5.2 算法思想

5.3 算法分析

5.4 试验结果

5.5 试验对比分析

5.6 结论

第六章 总结与展望

参考文献

致谢

攻读硕士学位期间发表论文

攻读硕士学位期间参与的工作

学位论文评阅及答辩情况表