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

摘要

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