Current Research in Bioinformatics

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

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

DOI : 10.3844/ajbsp.2012.50.63

Current Research in Bioinformatics

Volume 1, Issue 1

Pages 50-63

Abstract

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.

Copyright

© 2012 Evandro A. Marucci, Geraldo F.D. Zafalon, Julio C. Momente, Alex R. Pinto, Jose R.A. Amazonas, Yang Shiyou, Liria M. Sato and Jose M. Machado. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.