多序列比对是两个以上DNA序列、RNA序列或蛋白质序列的比对。多序列比对是基因组分析和蛋白质组分析的最常用手段之一,能有效发掘多个序列中的相似性信息。作为其他算法的基础,多序列比对软件必须具备快速比对数以十亿计的高度相似序列的能力,才能满足其他序列分析工具对性能和吞吐量的需求。目前的大多数相关软件并不能解决这一问题。本文从算法改进和并行加速两个方面进行深入研究,使用更高效的基于后缀树的多序列比对算法和并行加速技术提升算法的性能,使用Spark分布式框架解决程序对吞吐量的要求。具体工作如下:1.设计并实现了基于后缀树的双序列比算法,该算法是对传统的动态规划算法的改进。针对高度相似序列的特殊性质,该算法利用了后缀树强大的字符串处理能力加速双序列比对过程,通过一次查找序列,找出两序列中所有相互匹配的片段,大幅度减少使用动态规划算法比对片段的长度,降低了算法的时间复杂度。2.以中心星比对策略和基于后缀树的双序列比对算法为基础,设计基于后缀树的多序列比对算法MASC。中心星比对策略是一种高性能的多序列比对策略,但其预处理过程耗时过长。针对该问题,我们提出在比对同源序列时,随机选择中心序列不会造成精度损失。实验结果表明,MASC可以在线性时间完成同源序列的比对并且不会产生精度损失。3.在Spark平台上设计实现基于后缀树的多序列比对软件MASC-Spark。通过规划和调度RDD,最大化地发挥Spark框架的并行计算能力,进一步加速比对过程。在并行加速下,MASC-Spark的计算速度和吞吐量进一步提升。实验表明,该程序具有较好的加速比和可扩展性。