双序列比对算法研究与并行优化

论文摘要

双序列比对是生物信息处理中最基本的问题,是生物信息学重要的研究内容。评价生物序列比对算法有两个标准，一是算法的运算速度，二是获得最佳比对结果的敏感性。随着生物学数据的大量积累，对序列比对算法对运算速度提出了更高的要求，开发高效率的算法成为双序列比对研究中的瓶颈问题。双序列比对基本的算法是Needleman-Wunsch算法，该算法有两步：第一步根据动态规划思想计算得分矩阵，第二步由得分矩阵回溯得到最优比对。理论上分析，计算得分矩阵占用Needleman-Wunsch算法大量时间。针对这一问题，本文基于多核体系结构，对Needleman-Wunsch算法进行了并行优化。其基本思想是采用流水线技术，利用多线程分行计算得分矩阵。为减少线程间的交互时间，在计算得分矩阵过程中采用分块技术。在真实DNA序列上进行序列比对的实验结果表明，Needleman-Wunsch算法的并行优化算法时间开销减小，得到较高的加速比。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 双序列比对算法的研究现状
• 1.3 本文研究的内容
• 第二章 双序列比对问题综述
• 2.1 双序列比对问题描述
• 2.2 双序列比对问题的数学定义
• 2.3 比对分数矩阵和空位罚分
• 2.4 小结
• 第三章 基于动态规划的双序列比对算法研究
• 3.1 动态规划及分类
• 3.2 Needleman-Wunsch 算法
• 3.3 Hirschberg 算法
• 3.3.1 理论基础
• 3.3.2 算法描述及示例
• 3.4 实验
• 3.5 小结
• 第四章 双序列比对的并行优化算法
• 4.1 并行平台及分类
• 4.1.1 共享存储模型
• 4.1.2 消息传递模型
• 4.2 并行程序的性能
• 4.3 基于消息传递模型的 Needleman-Wunsch 算法的并行优化
• 4.3.1 消息传递模型的并行程序评估
• 4.3.2 Needleman-Wunsch 算法的并行优化算法描述及分析
• 4.4 基于多核流水线的 Needleman-Wunsch 算法的优化
• 4.4.1 流水线技术
• 4.4.2 Needleman-Wunsch 算法基于多核流水线的优化
• 4.4.3 算法基于分块技术的改进
• 4.5 实验及分析
• 4.6 小结
• 第五章 总结和展望
• 致谢
• 参考文献