预测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 结论
• 第六章 总结与展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表论文
• 攻读硕士学位期间参与的工作
• 学位论文评阅及答辩情况表