生物信息学是一门生命科学与计算机科学相结合而形成的新学科,是当今科学的研究热点之一。生物序列比对是生物信息学领域重要的基础研究,它不仅为进化分析、模体(motif)识别、RNA和蛋白质结构预测提供丰富的信息,还是生物保护、疾病控制等方面研究的基本工具。在高吞吐量的基因时代,随着大规模测序工作的日益成熟,序列比对的方式己发生巨大变化。过去几十年,比较一个给定基因的所有直系同源基因仅需要与几千条序列进行比对。而在未来几十年,可能需要比对几十亿条相关联的序列,这使得序列比对越来越复杂、耗时,现有的一些序列比对算法已经不适用于处理大规模序列数据。另一方面,多核计算机、集群、CPU+GPU异构系统等高性能计算平台的发展,给快速高效地处理大规模数据带来了巨大的机遇和挑战。由于序列比对应用的广泛性、计算的复杂性以及海量的数据特征,对计算机性能提出了越来越高的要求,迫切需要高性能计算的支持。本文将应用多核计算机和CPU+GPU异构系统解决大规模序列比对问题,主要研究工作如下:(1)针对序列比对算法的可扩展性问题,提出基于分治法的序列比对通用算法(DCPA)。通过将大规模序列集分割成能被现有算法处理的小的序列子集,在多核计算机实现大规模序列数据的处理。分别使用基准多序列比对库和大规模序列集测试DCPA算法的性能。实验结果表明,相对于经典的序列比对算法MUSCLE,DCPA获得了近81倍的性能加速,且维持较好的比对精度。(2)针对DCPA算法由于序列集划分不准确而导致的比对精度下降的问题,进一步研究序列集分割策略,提出基于数据并行的序列比对算法(CDAM)。CDAM算法应用聚类方法分割序列集,设计最长处理时间优先算法(LPT)分发序列子集,以及设计渐进式序列子集合并策略获得大规模序列集的比对结果。在CDAM的序列集分割阶段分别应用Cd-hit,UCLUST,SiLiX,CLUSS和BLASTClust等5种聚类方法,实验结果表明,聚类方法将影响CDAM的比对精度和比对时间。在这5种应用不同聚类方法的CDAM程序中,CDAM(UCLUST)和CDAM(Cd-hit)整体性能良好。相对于经典的序列比对算法MUSCLE,它们分别获得了 151倍和111倍的性能加速,损失了 2.19%和2.87%的比对精度。(3)针对MAFFT算法准确比对时间较长的问题,充分利用GPU提供的强大计算能力,提出基于CPU+GPU异构系统的MAFFT序列比对并行算法。通过设计异构系统负载平衡方法和内存优化策略,来消除GPU内存访问带宽瓶颈,减少内存消耗,从而获得其比对速度的大幅度提升。首先,优化序列的存储,设计异构系统负载平衡方法;然后,设计异构系统内存优化方法,包括满足合并访问条件的序列存储方法、相似矩阵存储和访问方式、得分矩阵压缩存储,解决由于异构系统存储空间的匮乏而导致的实际计算性能低下;最后,基于内存预分配和复用策略,提出粗粒度序列比对并行算法。分别在NVIDIA Tesla C2050、Tesla M2090和TeslaK20mGPU上测试基于异构系统的MAFFT序列比对并行算法。与串行和多线程MAFFT算法相比,在维持相同比对精度的同时,在Tesla K20m GPU上分别获得了 56.7倍和7.1倍的性能加速。(4)应用基于化学反应的优化方法,提出一种新的多序列比对算法(CROMSA)。通过对分子编码、群体初始化、目标函数、分子的撞墙、分解、合成、交换等分子基本操作的精心设计,来提高比对精度。使用基准多序列比对库测量CROMSA的比对精度和计算复杂度。实验结果表明,CROMSA在比对精度上优于本文提出的DCPA、CDAM(Cd-hit)、和CDAM(UCLUST)。由于需要花费较长时间来优化比对结果,CROMSA较这些算法比对时间长。但相对于当前其他流行算法ProbCons和MUMMALS,CROMSA具有明显的比对时间优势,进一步说明了应用化学优化方法求解序列比对问题的有效性。