Fast Parallel Maximum Likelihood-based Protein Phylogeny.

C. Blouin, D. Butt, G. Hickey, A. Rau-Chaplin.

Abstract: Inferring phylogenetic relationships between sequences is a difficult and interesting problem. Assuming that there is enough phylogenetic signal in biological sequence to resolve every tree bifurcation, the resulting tree is a representation of the vertical descent history of a gene. A popular method to evaluate a candidate phylogenetic tree uses the likelihood of the data, given an empirical model of character substitution. The computational cost of search for the maximum-likelihood tree is, however, very large. In this paper, we present an algorithm for protein phylogeny using a maximum likelihood framework. A key design goal, which differentiates our method from others, is that it determines a range (confidence set) of statistically equivalent trees, instead of only a single solution. We also present a number of sequential algorithmic enhancements and both sequential and parallel performance results.