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

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多个例子比较了两种算法的优劣。

论文目录

  • 摘要
  • Abstract
  • 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 比较分析
  • 结束语
  • 参考文献
  • 致谢
  • 攻读学位期间发表的学术论文
  • 学位论文评阅及答辩情况表
  • 相关论文文献

    标签:;  ;  ;  ;  ;  

    RNA二级结构预测的快速计算
    下载Doc文档

    猜你喜欢