Title :
Hybrid MPI/OpenMP Strategy for Biological Multiple Sequence Alignment with DIALIGN-TX in Heterogeneous Multicore Clusters
Author :
de Araujo Macedo, E. ; Magalhaes Alves de Melo, Alba Cristina ; Pfitscher, Gerson Henrique ; Boukerche, Azzedine
Author_Institution :
Dept. of Comput. Sci., Univ. of Brasilia (UnB), Brasilia, Brazil
Abstract :
Multiple Sequence Alignment (MSA) is a fundamental problem in Bioinformatics that aims to align more than two biological sequences in order to emphasize similarity regions. This problem is known to be NP-Complete, so heuristic methods are used to solve it. DIALIGN-TX is an iterative heuristic method for MSA that is based on dynamic programming and generates alignments by concatenating ungapped regions with high similarity. This paper proposes an MPI/OpenMP master/slave parallel strategy to run DIALIGN-TX in heterogeneous multicore clusters, with multiple allocation policies. The results obtained in a 28-core heterogeneous cluster with real sequence sets show that the execution time can be drastically reduced. Also, we show that an appropriate choice of the allocation policy and the master node has great impact on the overall system performance.
Keywords :
bioinformatics; computational complexity; dynamic programming; iterative methods; message passing; multiprocessing systems; 28-core heterogeneous cluster; DIALIGN-TX iterative heuristic method; MPI-OpenMP strategy; NP-complete problem; bioinformatics; biological multiple sequence alignment problem; dynamic programming; heterogeneous multicore clusters; master-slave parallel strategy; message passing interface; Bioinformatics; Biology; Message passing; Multicore processing; Program processors; Resource management;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.169
