【作者】 陈宁涛； 王能超； 施保昌；

【Author】 Chen Ningtao Wang Nengchao Shi Baochang School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan Hubei 430074, China Parallel Computing Institute, Huazhong University of Science & Technology, Wuhan Hubei 430074, China

【机构】 华中科技大学计算机科学与技术学院； 华中科技大学并行计算研究所；

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

【Abstract】 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.更多还原