RNA序列比对算法研究

论文摘要

生物信息学是一门综合利用生物学、计算机科学、数学等学科知识的新兴交叉学科。RNA序列比对是生物信息学研究的重要课题,特别是包含二级和三级结构的比对。由于RNA序列数据量大,折叠的结构非常复杂,造成序列的比对是一个复杂度高而又很难有实际检验的过程,其中RNA三级结构比对是NP-hard问题。如何提高序列比对的速度,以及解决三级结构比对问题是本课题研究的重点。本文在深入分析现有比对算法及其实现软件的基础上,利用RNA二级树形结构模型,深入分析了RNA二级结构对比对算法,对算法进行详细的阐述与分析。论文针对RNA三级结构比对难点,提出了基于二级结构映射的序列三级结构比对算法,以及基于二级结构转化的三级结构比对算法,对比对结果进行了分析。论文对算法的实现及其比对软件的测试结果也作了深入的分析,实验结果表明二级结构比对算法具有较好的时间特性;三级结构比对算法能够正确反映序列的相似度,并且和二级结构密切相关。在实现的过程中,还针对RNA海量数据的特点,提出内存优化和动态规划回溯优化策略,提高了处理的效率。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 项目研究背景
• 1.1.1 课题背景
• 1.1.2 国内外研究现状与水平
• 1.1.3 项目的提出
• 1.2 项目研究意义
• 1.2.1 项目应用现状
• 1.2.2 项目研究意义
• 1.3 项目研究内容及主要贡献
• 1.4 论文组织结构
• 第二章 基于树形结构的RNA二级比对算法
• 2.1 RNA序列比对模型
• 2.1.1 序列结构
• 2.1.2 序列突变与序列操作
• 2.1.3 RNA序列比对问题
• 2.1.4 已有算法分析
• 2.2 序列比对的算法基础
• 2.2.1 动态规划算法思想
• 2.2.2 序列比对的动态规划
• 2.2.3 RNA一级结构的动态规划处理
• 2.3 RNA二级结构比对算法
• 2.3.1 RNA树形结构表达
• 2.3.2 动态规划表的构建
• 2.3.3 算法描述
• 2.4 小结
• 第三章 基于RNA二级结构的RNA三级结构比对算法
• 3.1 RNA结构映射和约束距离
• 3.1.1 二级结构映射
• 3.1.2 基于映射的约束距离
• 3.2 基于RNA二级结构映射的三级结构比对算法
• 3.2.1 动态规划表的构建
• 3.2.2 算法描述
• 3.2.3 比对结果分析
• 3.3 基于RNA二级结构变换的三级结构比对算法
• 3.3.1 RNA三级结构的变换
• 3.3.2 算法描述
• 3.3.3 比对结果分析
• 3.4 小结
• 第四章 序列比对算法实现技术研究
• 4.1 RNA数据结构分析和处理
• 4.1.1 RNA数据分析
• 4.1.2 RNA树形结构预处理
• 4.1.3 罚分函数设计和比对方式评价
• 4.2 数组操作和内存管理
• 4.2.1 快速排序与折半查找结合的数组操作
• 4.2.2 内存管理和编译技术
• 4.3 序列比对算法的实现
• 4.3.1 动态规划得分矩阵改进
• FA算法'>4.3.2 UKK_FA算法
• 4.3.3 优化的回溯路径
• 4.4 实验结果分析
• 4.5 小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 将来进一步的研究工作
• 参考文献
• 致谢
• 攻读硕士期间主要的研究成果