Hybrid MPI/OpenMP Strategy for Biological Multiple Sequence Alignment with DIALIGN-TX in Heterogeneous Multicore Clusters

摘要

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.