Research Article Open Access

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

Evandro A. Marucci1, Geraldo F.D. Zafalon1, Julio C. Momente1, Alex R. Pinto1, Jose R.A. Amazonas2, Yang Shiyou3, Liria M. Sato2 and Jose M. Machado1
  • 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.

Current Research in Bioinformatics
Volume 1 No. 1, 2012, 50-63

DOI: https://doi.org/10.3844/ajbsp.2012.50.63

Submitted On: 28 February 2012 Published On: 8 March 2012

How to Cite: Marucci, E. A., Zafalon, G. F., Momente, J. C., Pinto, A. R., Amazonas, J. R., Shiyou, Y., Sato, L. M. & Machado, J. M. (2012). Using Threads to Overcome Synchronization Delays in Parallel Multiple Progressive Alignment Algorithms. Current Research in Bioinformatics, 1(1), 50-63. https://doi.org/10.3844/ajbsp.2012.50.63

  • 6,005 Views
  • 4,242 Downloads
  • 3 Citations

Download

Keywords

  • Sequence alignment algorithms
  • Hidden Markov Models (HMM)
  • performance remarkably
  • progressive approach
  • computational complexity
  • represent genetic