生物多序列比对的并行算法

多序列比对是生物信息学中的基本问题。由于生物序列数据库的快速增长，即使优秀的串行算法已不能满足实际的需要。研究了Gusfield提出的星型比对模型的串行算法，进行了空间和时间上的改进，基于cluster结构的菜并行机提出了一种并行算法，并对大量基因数据进行了测试，结果表明对于大规模的多序列比对，算法能达到较高的加速比。

PARALLEL ALGORITHM FOR BIOLOGICAL MULTIPLE SEQUENCE ALIGNMENTS

Multiple sequence alignments (MSA) are the basic problem of bioinformatics. Due to the rapid growth of sequence databases, many good serial algorithms for MSA might not satisfy the practical application, so it is necessary to study the parallel algorithm. The central star model proposed by Gusfield is studied and implemented in this paper and is optimized in space and time. A parallel scheme is introduced based on the improved central star algorithm on a cluster structure machine. Many gene datasets are selected to test the parallel algorithm. Experimental results indicate that the proposed algorithm can achieve higher speed-up ratio for high scale MSA problem.