Using Threads to Overcome Synchronization Delays in Parallel Multiple Progressive Alignment Algorithms | Science Publications

American Journal of Bioinformatics

Alex R. Pinto¹  Yang Shiyou¹  Evandro A. Marucci¹  Liria M. Sato¹  Jose R.A. Amazonas¹  Julio C. Momente¹  Geraldo F.D. Zafalon¹  Jose M. Machado¹ 

关键词: Sequence alignment algorithms;    Hidden Markov Models (HMM);    performance remarkably;    progressive approach;    computational complexity;    represent genetic;   

DOI  :  10.3844/ajbsp.2012.50.63

学科分类：生物技术

来源: Science Publications

【 摘 要 】

Problem statement: The parallelization of multiple progressive alignment algorithms is a difficult task. All known methods have strong bottlenecks resulting from synchronization delays. This is even more constraining in distributed memory systems, where message passing also delays the interprocess communication. Despite these drawbacks, parallel computing is becoming increasingly necessary to perform multiple sequence alignment. Approach: In this study, it is introduced a solution for parallelizing multiple progressive alignments in distributed memory systems that overcomes such delays. Results: The proposed approach uses threads to separate actual alignment from synchronization and communication. It also uses a different approach to schedule independent tasks. Conclusion/Recommendations: The approach was intensively tested, producing a performance remarkably better than a largely used algorithm. It is suggested that it can be applied to improve the performance of some multiple alignment tools, as CLUSTALW and MUSCLE.

【 授权许可】

Unknown