RNA二级结构预测算法研究

论文摘要

RNA二级结构预测是生物信息学的重要研究领域。本文从不同的角度出发,提出了三种类型的用于RNA二级结构预测的方法。首先提出了基于茎区的动态规划算法的RNA二级结构预测方法：该方法以茎区为最小结构单元,根据每个茎区形成的环的大小计算该茎区的能量并保存,之后构造动态规划方法,该方法的优势是能够得到能量最优的二级结构；提出了基于蚁群算法的RNA二级结构预测方法：该方法在选择下一茎区时能够利用茎区和茎区之间的累积的信息,且能够采用更准确的多分枝环的能量计算公式,在得到初始的二级结构后,通过延伸茎区的策略得到最终的二级结构；在蚁群算法的基础上,提出了改进的模糊蚁群算法的RNA二级结构预测方法,该方法一定程度上提高了蚁群算法的效率和寻优能力；最后提出了基于框架的RNA二级结构预测方法：该方法仅以最小自由能为辅助,根据能量次优的二级结构得到茎区的分布情况,由出现次数较多的茎区生成二级结构的框架,之后向该框架中添加相容的茎区,最终输出每个二级结构及其出现的次数,该方法一定程度上避免了最小自由能本身参数不准确性的影响。

论文目录

• 提要
• 摘要
• Abstract
• 第1章 绪论
• 1.1 背景介绍
• 1.2 RNA二级结构预测方法
• 1.2.1 多序列比对算法
• 1.2.2 动态规划方法
• 1.2.3 遗传算法
• 1.2.4 随机上下文无关文法
• 1.2.5 随机堆积方法
• 1.3 基本概念
• 1.3.1 茎区之间的关系
• 1.3.2 RNA二级结构
• 1.4 最小自由能
• 1.4.1 发卡环
• 1.4.2 凸环
• 1.4.3 茎区
• 1.4.4 内环
• 1.4.5 多分枝环
• 1.4.6 小结
• 第2章 基于茎区的动态规划算法的RNA二级结构预测
• 2.1 编码规则
• 2.1.1 编码方式
• 2.1.2 编码关联表
• 2.1.3 匹配表
• 2.2 基于茎区的动态规划算法
• 2.2.1 相关定义
• 2.2.2 算法描述
• 2.2.3 RNAstem算法的流程
• 2.3 实验结果
• 2.3.1 与组合优化算法的比较
• 2.3.2 与传统动态规划算法的比较
• 2.4 本章小结
• 第3章 基于蚁群算法的RNA二级结构预测
• 3.1 蚁群算法的起源
• 3.2 基于蚁群算法的RNA二级结构预测
• 3.2.1 启发式信息
• 3.2.2 初始信息素
• 3.2.3 选择初始茎区
• 3.2.4 选择下一茎区
• 3.2.5 信息素的更新机制
• 3.2.6 算法流程图
• 3.3 实验结果
• 3.3.1 参数λ的选择
• 3.3.2 参数Q的选择
• 3.3.3 与RNAstructure和GA的比较
• 3.4 本章小结
• 第4章 基于茎区的模糊蚁群算法的RNA二级结构预测
• 4.1 模糊自适应的蚁群算法
• 4.1.1 选择初始结点
• 4.1.2 启发式信息
• 4.1.3 选择下一结点
• 4.1.4 模糊自适应机制
• 4.1.5 精英结点策略
• 4.1.6 系统更新策略
• 4.1.7 关于信息素挥发系数的思考
• 4.1.8 模糊蚁群算法的流程图
• 4.2 模糊蚁群算法的性能研究
• 4.2.1 参数α和β的确定
• 4.2.2 算法寻优能力的比较
• 4.2.3 算法收敛速度的比较
• 4.2.4 bays29的最优路径
• 4.2.5 eil51的最优路径
• 4.3 基于模糊蚁群算法的RNA二级结构预测
• 4.3.1 选择初始茎区
• 4.3.2 延伸茎区的策略
• 4.3.3 和传统蚁群算法的比较
• 4.4 本章小结
• 第5章 基于框架的RNA二级结构预测
• 5.1 RNA茎区和结构问题研究
• 5.1.1 总茎区个数和RNA序列长度的关系
• 5.1.2 茎区的分布情况
• 5.1.3 RNA二级结构总个数和序列长度的关系
• 5.1.4 二级结构的能量分布图
• 5.1.5 不同能量下的茎区分布图
• 5.2 RNAframe算法
• 5.2.1 RNAframe算法的流程
• 5.2.2 与茎区随机堆积算法的比较
• 5.3 实验结果
• 5.4 本章小结
• 第6章 结论与展望
• 参考文献
• 作者简介及在学期间所取得的科研成果
• 致谢