异构机群系统上序列比对并行处理研究

论文摘要

序列比对是生物信息学的核心研究内容之一,也是各种序列分析任务的基本方法。它研究序列之间的优化对应,即用一个距离函数或者相似分数来度量序列之间的相似性和非相似性。序列比对对研究分子结构与功能预测具有重要意义,因此其计算方法得到人们高度重视。在实际应用中,序列比对的规模很大,即使利用最快的串行比对算法也很耗时,因此需要设计高效的并行算法以快速求解这类问题。由于机群计算系统具有高性能和低成本的特点,所以在异构机群系统上研究序列比对算法的并行处理具有重要的现实意义。本文基于可分负载理论的最优原则,对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,与平均分配策略相比,本文提出的最优分配策略进行双序列全局比对并行处理所需的时间明显缩短,并获得良好的加速和可扩展性。多序列局部比对是另一个重要的序列比对问题。本文针对处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,给定处理机分配顺序,基于可分负载理论提出一种多序列局部比对问题并行处理的最优分配策略,给定了处理机最优分配顺序,给出并行求解多序列局部比对问题所需时间的数学规划模型。异构PC机群系统上的实验结果表明,本文提出的最优分配策略进行多序列局部比对并行处理所需的时间比按平均分配策略的算法所需时间短,并获得良好的加速和可扩展性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 序列比对问题的相关概念
• 1.2.1 序列比对问题的生物学背景
• 1.2.2 序列比对的基本概念
• 1.2.3 动态规划算法
• 1.2.4 全局比对和局部比对
• 1.2.5 空位罚分和替换矩阵
• 1.2.6 启发式算法
• 1.3 序列比对研究与发展
• 1.3.1 国外研究现状
• 1.3.2 国内研究现状
• 1.4 论文的主要研究内容和贡献
• 1.5 论文的组织
• 第二章 并行计算基础
• 2.1 并行算法的概念和复杂性度量
• 2.1.1 并行算法概念和分类
• 2.1.2 并行算法的性能评价标准
• 2.2 并行计算模型
• 2.2.1 PRAM模型
• 2.2.2 分布存储SIMD模型
• 2.2.3 异步APRAM模型
• 2.2.4 BSP模型
• 2.2.5 LogP模型
• 2.2.6 可重构MESH互联的光计算模型
• 2.2.7 Cell Matrix模型
• 2.3 机群系统概述
• 2.4.1 机群系统特点
• 2.4.2 机群系统分类
• 2.4.3 机群技术发展现状
• 2.4.4 机群系统的组建
• 第三章 双序列全局比对并行算法在异构机群上的设计与实现
• 3.1 引言
• 3.2 双序列全局比对串行算法
• 3.3 可分负载理论与异构机群系统上双序列全局比对并行算法
• 3.3.1 双序列全局比对并行处理的最优分配策略
• 3.3.2 分配给从处理机的子序列长度和并行迭代次数的确定
• 3.4 实验结果和分析
• 3.5 本章小结
• 第四章 异构机群系统上多序列局部比对并行算法
• 4.1 引言
• 4.2 多序列局部比对算法的分析
• 4.3 异构机群系统上BLAST算法的并行处理
• 4.3.1 BLAST并行算法的设计与分析
• 4.3.2 BLAST并行算法的序列串最优分配策略
• 4.4 实验结果和分析
• 4.5 本章小结
• 第五章 总结
• 5.1 本文的主要工作和贡献
• 5.2 下一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间参加的科研项目
• 攻读硕士学位期间发表/录用的学术论文