Rapid evaluation of least squares and minimum evolution criteria on phylogenetic trees

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. These include: an optimal O(N² ) time algorithm for calculating the branch (edge) lengths on a tree according to ordinary or unweighted least squares (OLS); an O(N³ ) time algorithm for edge lengths under weighted least squares (WLS) and the FitchMargoliash method; and an optimal O(N⁴) time algorithm for generalised least squares edge lengths. The Minimum Evolution criterion is based on the sum of edge lengths. Consequently, the edge lengths algorithms presented here lead directly to O(N² ), O(N³ ) and O(N⁴) time algorithms for ME under OLS, WLS and GLS respectively. These algorithms are substantially faster than all those previously published, and the algorithms for OLS and GLS are the fastest possible (with respect to order of computational complexity). An optimal algorithm for determining path lengths in a tree with given edge lengths is also developed. This leads to an optimal O(N² ) algorithm for OLS sums of squares evaluation and corresponding O(N³ ) and O(N⁴) time algorithms for WLS and GLS sums of squares, respectively. The GLS algorithm is time optimal if the covariance matrix is already inverted. The considerable increases in speed enable far more extensive tree searches and statistical evaluations (e.g. bootstrap, parametric bootstrap or jackknife). Hopefully, the fast algorithms for WLS and GLS will encourage their use for evaluating trees and their edge lengths ( e.g. for approximate divergence time estimates), since they should be more statistically efficient than OLS