面向异构并行系统的生物序列比对并行策略及算法研究

序列比对是生物信息学中重要的基本问题,是生物信息学的基础,可用来预测序列的功能、结构和进化过程等. 随着大规模测序技术日益成熟,序列数据呈指数级增长,使得现有序列比对并行策略中存在的可扩展性问题日益突出.同时,现有的序列比对并行策略多使用同构系统求解,且极少采用数据并行方案. 随着高性能计算系统快速发展,应用异构并行系统求解各类NP难解问题已变得越来越普及和流行. 本项研究将在异构并行系统中求解序列比对问题.首先提出一种异构并行系统计算能力描述模型,然后设计基于聚类的新的数据并行策略,最后通过0-1整数规划求解并行调度最优解,并设计近似最优的启发式算法.本项研究不仅为生物序列比对基于异构超级计算机的并行化策略和方法奠定基础,为生物信息学中数据密集应用提供高性能计算解决方法,还将拓宽超级计算机应用领域,推动生物信息学的研究与发展.

面向异构并行系统的序列比对并行策略研究，不仅设计异构并行系统计算能力描述模型，还为序列比对的并行策略和算法设计提供新思路，从而为生物信息学的更广泛应用奠定基础；同时还将丰富传统并行处理的研究内容，推动生物信息学和高性能计算与超级计算机系统的研究与发展。.本项目（1）针对序列比对算法的可扩展性问题，提出基于分治法的序列比对通用算法(DCPA)。通过将大规模序列集分割成能被现有算法处理的小的序列子集，在多核计算机实现大规模序列数据的处理。分别使用基准多序列比对库和大规模序列集测试DCPA算法的性能。实验结果表明，相对于经典的序列比对算法MUSCLE，DCPA获得了近111倍的性能加速，且维持较好的比对精度。.（2）进一步研究序列集分割策略，提出基于数据并行的序列比对算法(CDAM)。CDAM算法应用聚类方法分割序列集，设计最长处理时间优先算法(LPT)分发序列子集，以及设计渐进式序列子集合并策略获得大规模序列集的比对结果。分别应用Cd-hit，UCLUST，SiLiX，CLUSS和BLASTClust等5种聚类算法到CDAM的序列集分割阶段。实验结果表明：在这5种应用不同聚类方法的CDAM程序中，CDAM(UCLUST)和CDAM(Cd-hit) 整体性能良好。相对于经典的序列比对算法MUSCLE，它们分别获得了151倍和111倍的性能加速，损失了2.19%和2.87%的比对精度。.（3）提出基于CPU+GPU异构系统的MAFFT序列比对并行算法。分别在NVIDIA Tesla C2050、Tesla M2090和Tesla K20m GPU上测试基于异构系统的MAFFT序列比对并行算法。与串行和多线程MAFFT算法相比，在维持相同比对精度的同时，在Tesla K20m GPU上分别获得了56.7和7.1的性能加速。.（4）提出一种新的多序列比对算法(CROMSA)。使用基准多序列比对库测量CROMSA的比对精度和计算复杂度。实验结果表明，CROMSA在比对精度上优于本文提出的DCPA、CDAM(Cd-hit)、和CDAM(UCLUST)。由于需要花费较长时间来优化比对结果，CROMSA较这些算法比对时间长。但相对于当前其他流行算法ProbCons和MUMMALS，CROMSA具有明显的比对时间优势，进一步地说明了应用化学优化方法求解序列比对问题的有效性。