Mol. Biol. Evol. 15(10):1346-1359. 1998
DOI:
© 1998 by the Society for Molecular Biology and Evolution. ISSN: 0737-4038
Rapid Evaluation of Least-Squares and Minimum-Evolution Criteria on Phylogenetic Trees
Biomathematics Research Centre, University of Canterbury, Christchurch, New Zealand
E-mail: bryant{at}crm.umontreal.ca.
We present fast new algorithms for evaluating trees with respect to least squares and minimum evolution (ME), the most commonly used criteria for inferring phylogenetic trees from distance data. The new algorithms include an optimal O(N2) time algorithm for calculating the edge (branch or internode) lengths on a tree according to ordinary or unweighted least squares (OLS); an O(N3) time algorithm for edge lengths under weighted least squares (WLS) including the Fitch-Margoliash method; and an optimal O(N4) time algorithm for generalized least-squares (GLS) edge lengths (where N is the number of taxa in the tree). The ME criterion is based on the sum of edge lengths. Consequently, the edge lengths algorithms presented here lead directly to O(N2), O(N3), and O(N4) time algorithms for ME under OLS, WLS, and GLS, respectively. All of these algorithms are as fast as or faster than any of those previously published, and the algorithms for OLS and GLS are the fastest possible (with respect to order of computational complexity). A major advantage of our new methods is that they are as well adapted to multifurcating trees as they are to binary trees. An optimal algorithm for determining path lengths from a tree with given edge lengths is also developed. This leads to an optimal O(N2) algorithm for OLS sums of squares evaluation and corresponding O(N3) and O(N4) time algorithms for WLS and GLS sums of squares, respectively. The GLS algorithm is time-optimal if the covariance matrix is already inverted. The speed of each algorithm is assessed analytically—the speed increases we calculate are confirmed by the dramatic speed increases resulting from their implementation in PAUP* 4.0. The new algorithms enable far more extensive tree searches and statistical evaluations (e.g., bootstrap, parametric bootstrap, or jackknife) in the same amount of time. Hopefully, the fast algorithms for WLS and GLS will encourage the use of these criteria for evaluating trees and their edge lengths (e.g., for approximate divergence time estimates), since they should be more statistically efficient than OLS.
Key Words: least-squares method • minimum evolution • phylogenetic inference • tree statistics • algorithms
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  Combinatorics of least-squares trees PNAS, September 9, 2008; 105(36): 13206 - 13211.
|
|
|
|
 |
|
 M. D. Rasmussen and M. Kellis Accurate gene-tree reconstruction by learning gene- and species-specific substitution rates across multiple complete genomes Genome Res., December 1, 2007; 17(12): 1932 - 1942. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. J. Waddell, H. Kishino, and R. Ota Phylogenetic Methodology for Detecting Protein Interactions Mol. Biol. Evol., March 1, 2007; 24(3): 650 - 659. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Desper and O. Gascuel Theoretical Foundation of the Balanced Minimum Evolution Method of Phylogenetic Inference and Its Relationship to Weighted Least-Squares Tree Fitting Mol. Biol. Evol., March 1, 2004; 21(3): 587 - 598. [Abstract] [Full Text] [PDF]
|
|