Parallel Implementation of SEMPHY - a Structural EM Algorithm for Phylogenetic Reconstruction.
Abstract
Inference of phylogenetic trees based on the Maximal Likelihood method is computational ex-tremely intensive. In order to accelerate the computations, we present the parallel implementa-tion of SEMPHY in this paper. SEMPHY is a program for the phylogenetic reconstruction fromDNA/protein sequence data, which uses the structural expectation-maximization (SEM) algorithm,to efficiently search for maximum likelihood phylogenetic trees. It is dramatically faster than otherML methods while reserving comparable accuracy. Two different parallel paradigms, i.e., OpenMPand MPI version are developed to compare their performance on different parallel systems. Ourexperiments show that the OpenMP version scales well with the increase of processors on the sharedmemory system, and achieves better speedup than the MPI version on the cluster system.
