多序列比对是目前生物信息领域研究的重要课题之一,在基因识别、蛋白质结构预测等领域有着广泛的应用。由于问题本身所固有的复杂性,至今还没有一个令人满意的算法,同时随着生物数据的不断增长,串行算法已不能满足人们的需求。本课题重点研究了如何利用de Brujin图进行多序列比对及其并行化处理方案,提出了一个新的多序列比对并行算法PL_GAlign。课题的主要工作与贡献如下:在基于图论的算法中引入了距离参数并采用了改进的星形比对算法:详细分析了目前使用比较广泛的多序列比对算法,但是常用的并行划分策略对该类算法的执行效果较差。因此重点研究了基于图论的多序列比对算法并对其进行了改进:为了更好的适应基因的变异性,在该类算法中引入了距离参数d,将现有算法的精确匹配修改为允许一定误差的模糊匹配。在应用de Bruijn图得到中心序列后,摒弃了现有算法中常用的动态规划算法,采用了更为适合这种情况的星型比对算法并对其进行了改进,从而使该算法的时间复杂度降低至几乎线性。针对算法中的各个阶段提出了并行处理策略:针对多序列比对的高计算复杂性问题,研究了基于de Bruijn图的并行化处理方案。分别对基于图论的多序列比对算法中的构建de Bruijn图、去环、寻找最大权值路径和两两比对阶段的串行处理过程和可并行性进行了探讨,提出了各个阶段的并行处理策略。最后进行了一系列数据测试,实验结果证明PL_GAlign算法在运行速度上要优于现有的迭代法,尤其当输入序列较长且数目较多时,这种优势更为明显。在精度上略好于目前使用最广泛的CLUSTAL W算法。