Using Threads to Overcome Synchronization Delays in Parallel Multiple Progressive Alignment Algorithms
- 1 Sao Paulo State University, Brazil
- 2 University of Sao Paulo, Brazil
- 3 Zhejiang University, China
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.
DOI: https://doi.org/10.3844/ajbsp.2012.50.63
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.
- 7,183 Views
- 4,877 Downloads
- 3 Citations
Download
Keywords
- Sequence alignment algorithms
- Hidden Markov Models (HMM)
- performance remarkably
- progressive approach
- computational complexity
- represent genetic