A Three-Level Parallel Algorithm for MrBayes 3.2

摘要

MrBayes is a popular bioinformatics software that is widely used in phylogenetic analysis. The core algorithm of Mrbayes is Metropolis Coupled Markov Chain Monte Carlo (MC3). However, when dealing with large data sets, MC3 algorithm is too slow to meet researcher's requirements. Although several parallelizations have been proposed for MrBayes, such as MPI (Message Passing Interface) based MrBayes, GPU (Graphics Processing Unit) based MrBayes, there is still no efficient parallel algorithm to fully utilize computing power of modern CPU and computer architecture. This paper (a) presents a new three-level hybrid parallel algorithm, include data-level parallelism (DLP), thread-level parallelism (TLP), and process-level parallelism (PLP), which can be used on most modern multi-core computers; (b) compares the performance of different combinations of parallel strategies on real-world protein data sets. The experimental results show that, this hybrid parallel algorithm does convert more computing powers into higher speedup. Furthermore, the proposed algorithm's speedup is near the speedup on one GPU at the same data sets. This algorithm is fit for practical use in phylogenetic inferences.