随着人类基因组计划的顺利实施,生物数据海量增加,随后生物信息学开始迅速兴起。生物序列比对是目前生物信息学领域一个有难度却重要的研究课题,广泛的应用于基因识别和氨基酸结构预测等领域中。在很多种情况下,具有高相似性的大规模生物数据需要被分析处理。由于生物学本身的特点和海量生物数据的获得,到目前为止还没有一个方法可以满足各领域研究人员的需求,其中串行算法在处理生物数据时所表现的的低效率也困扰着研究人员。本文将着重考察利用并行计算来进行多序列比对及其并行化处理方案,对此提出了一个新的多序列比对并行算法P-MA。详细分析了目前使用比较广泛的多序列比对算法,其中,动态规划方法在处理序列优化时表现非常良好,然而由于它的平方级时间复杂度成为了进一步研究的瓶颈。人们开始寻求一种平衡,近似最优化情况下去提高算法运行速度。星比对方法经常被用来处理大规模序列数据。本文尝试了更为适合具有高相似性序列的星比对算法并进行了相应的改进,在基于改进的星形比对算法中引入了并行处理机制,从而使该算法的时间复杂度降低至几乎线性。首先一种针对此的多序列比对算法MA算法被提出,利用关键字树和滑动窗口来匹配r-length片段的子字符串而剩余片段使用动态规划比对,最终得到比对结果。这种方法提供参数调节机制,调节参数对于该算法的性能起着极重要的作用。实验结果充分说明了其在计算效率上的优势。尽管做了如上改进,时间需求仍然比较大,当在按照上面所介绍的方法进行比对时,发现对于条数很多的待比对序列在寻找中心序列时,会出现很多序列没有做任何事的情况,出现了很大的空隙。加上多序列比对的高计算复杂性问题,研究了基于MA算法的并行化处理策略。基于这些,本文提出P-MA来合理分配以及处理在寻找中心序列时出现的空闲,将原来需要串行处理的序列在不同的处理器上同时处理,找到中心序列后再做综合处理。该方法同样遵守滑动调节机制,在分配各处理器任务时特别注重合理性,因为运用并行计算本身会带来额外的开销,所以自我调节机制和任务分配对于P-MA是极其重要的。针对算法提出了并行处理策略：对基于并行计算的多序列比对方法依次进行了构建P-MA、改变参数和两两比对阶段的串行处理过程和可并行性进行了探讨,提出了各个阶段的并行处理策略。对以改进算法效率为目标的算法需要尽量将敏感度保证在可接受范围内,不能让最终的比对结果失去了研究价值和生物意义。为使多序列比对问题的时间复杂度降到了线性级,在中心序列获得后,最终我们会利用动态规划方法得到多序列比对结果,保证其优化程度。本文还改进了MA,充分将空闲序列利用起来。试验结果表明利用了并行机制的DNA多序列星比对算法是有效可行的,尤其是对于具有高相似性的序列数据。最终对一系列生物序列数据进行了试验,试验结果表明P-MA在计算效率上要优于OA(基于关键字树的DNA多序列星比对算法)和MA,尤其当输入序列较长且数目较多时,这种优势将会更为明显。而且在精度上同MA一样,同样将略微好于OA,这点这说明了算法不仅保证了敏感度,更提高了运行效率。