基于模拟退火的RNA二级结构预测算法研究

论文摘要

RNA分子在生物细胞中起着关键作用,分子中的碱基在氢键的作用下相互绑定形成不同的二级结构。虽然动态规划算法可以高效求解不含假结的二级结构,但RNA分子的假结对细胞功能具有重要影响,这种结构破坏了相互嵌套碱基对规则,使得传统的动态规划算法无法成功求解该问题。随着分子序列长度的增加,RNA分子的碱基配对组合呈指数量级增长,含假结的RNA二级结构预测问题已被证明为NP完全问题。目前,国内外许多研究者提出了许多不同的含假结的RNA二级结构预测算法,但是这些算法都存在着一些不足之处。其中,序列比较分析类的算法预测精度高,但是该算法依赖于大量已知的同源序列信息;动态规划类的算法收敛速度慢且在预测长链RNA序列时预测精度不高。因此,不论采用目前哪种算法进行预测仍存在一些问题,构建一个有效的算法来提高预测含假结的RNA分子二级结构的精确度就显得尤为重要。本文将预测问题转换成等价的组合优化问题后,提出了一种基于模拟退火的含假结的RNA二级结构预测算法。首先根据最小茎区长度和最小环区长度两个约束条件,设计了一种高效的碱基互补配对方式并为发生冲突的碱基提供了详细的冲突解决方案。然后将RNA序列的茎区数量和碱基配对总数作为评价RNA二级结构的因子,提出一种简单且有效的适应度评价函数。本文从PseudoBase数据库中随机选择了15个测试序列,并与IPknot、TT2NE和HotKnots等其他领先的预测算法进行对比实验,实验结果验证了本算法的有效性。根据上述评价函数的两个因子,可以将含假结的RNA二级结构预测问题转换成多目标最小化问题。因此本文在上述算法基础上,提出一种基于多目标模拟退火的长链RNA二级结构预测算法。首先详细定义了所提出算法不同解之间的支配关系,然后为确保帕托前沿上的解分布均匀,设计了一种增加RNA二级结构多样性的策略,最后通过近邻热力学参数计算出帕累托前沿中最稳定的RNA二级结构。与其它算法进行对比,实验结果表明本文所提出的算法具有预测长链RNA二级结构的能力。

论文目录

摘要

ABSTRACT

第1章绪论

1.1 研究背景及意义

1.2 含假结的RNA二级结构预测研究进展

1.2.1 基于序列比较分析预测算法

1.2.2 基于动态规划思想预测算法

1.2.3 基于启发式思想预测算法

1.3 论文组织结构

第2章模拟退火算法和多目标进化算法

2.1 模拟退火算法

2.1.1 模拟退火算法简介

2.1.2 模拟退火算法的特点

2.1.3 模拟退火算法的应用

2.2 多目标进化算法

2.2.1 多目标进化算法简介

2.2.2 多目标优化问题描述及相关定义

2.2.3 多目标进化算法的特点

2.2.4 多目标进化算法的应用

2.3 本章小结

第3章基于模拟退火的RNA二级结构预测算法

3.1 概述

3.2 RNA二级结构相关知识

3.2.1 RNA的基础知识

3.2.2 RNA二级结构定义

3.2.3 RNA二级结构的构成

3.2.4 RNA二级结构的图解表示

3.2.5 最小自由能

3.3 RNA二级结构预测问题描述

3.4 PRSA算法模型

3.4.1 计算K连续碱基对集合的算法实现

3.4.2 适应度函数

3.4.3 近邻状态和冲突处理

3.4.4 含假结的RNA二级结构预测算法实现

3.5 实验结果与分析

3.5.1 评价标准

3.5.2 数据集

3.5.3 对比方法

3.5.4 结果分析

3.6 本章小结

第4章基于多目标模拟退火的RNA二级结构预测算法

4.1 概述

4.2 基于多目标的RNA二级结构预测问题描述

4.3 PRMOSA算法模型

4.3.1 PRMOSA算法的总体设计

4.3.2 PRMOSA算法的收敛性

4.3.3 RNA二级结构的非支配排序

4.3.4 RNA二级结构的多样性

4.4 实验结果比较与分析

4.5 本章小结

第5章结论与展望

致谢

参考文献

附录1 攻读硕士学位期间发表的论文

附录2 攻读硕士学位期间参加的科研项目

文章来源

类型: 硕士论文

作者: 吕育林

导师: 张凯

关键词: 二级结构,假结,模拟退火算法,多目标模拟退火算法

来源: 武汉科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 生物学,自动化技术

单位: 武汉科技大学

分类号: TP18;Q522

总页数: 64

文件大小: 2514K

下载量: 82

基于模拟退火的RNA二级结构预测算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢