Stochastic Search Strategy for Estimation of Maximum Likelihood Phylogenetic Trees

Abstract.—The maximum likelihood (ML) method of phylogenetic tree construction is not as widely used as other tree construction methods (e.g., parsimony, neighbor-joining) because of the prohibitive amount of time required to �nd the ML tree when the number of sequences under consideration is large. To overcome this dif�culty, we propose a stochastic search strategy for estimation of the ML tree that is based on a simulated annealing algorithm. The algorithm works by moving through tree space by way of a “local rearrangement ” strategy so that topologies that improve the likelihood are always accepted, whereas those that decrease the likelihood are accepted with a probability that is related to the proportionate decrease in likelihood. Besides greatly reducing the time required to estimate the ML tree, the stochastic search strategy is less likely to become trapped in local optima than are existing algorithms for ML tree estimation. We demonstrate the success of the modi�ed simulated annealing algorithm by comparing it with two existing algorithms (Swofford’s PAUP ¤ and Felsenstein’s DNAMLK) for several theoretical and real data examples. [Maximum likelihood; simulated annealing; stochastic probing; stochastic search.] A great variety of methods for estimating phylogenetic trees from DNA or RNA sequence data are currently available. Among these, the maximum likelihood (ML) method has several advantages, including statistical