Rapid maximum likelihood ancestral state reconstruction of continuous characters: A rerooting-free algorithm

Abstract

Ancestral state reconstruction is a method used to study the evolutionary trajectories of quantitative characters on phylogenies. Although efficient methods for univariate ancestral state reconstruction under a Brownian motion model have been described for at least 25 years, to date no generalization has been described to allow more complex evolutionary models, such as multivariate trait evolution, non-Brownian models, missing data, and within-species variation. Furthermore, even for simple univariate Brownian motion models, most phylogenetic comparative R packages compute ancestral states via inefficient tree rerooting and full tree traversals at each tree node, making ancestral state reconstruction extremely time-consuming for large phylogenies. Here, a computationally efficient method for fast maximum likelihood ancestral state reconstruction of continuous characters is described. The algorithm has linear complexity relative to the number of species and outperforms the fastest existing R implementations by several orders of magnitude. The described algorithm is capable of performing ancestral state reconstruction on a 1,000,000-species phylogeny in fewer than 2 s using a standard laptop, whereas the next fastest R implementation would take several days to complete. The method is generalizable to more complex evolutionary models, such as phylogenetic regression, within-species variation, non-Brownian evolutionary models, and multivariate trait evolution. Because this method enables fast repeated computations on phylogenies of virtually any size, implementation of the described algorithm can drastically alleviate the computational burden of many otherwise prohibitively time-consuming tasks requiring reconstruction of ancestral states, such as phylogenetic imputation of missing data, bootstrapping procedures, Expectation-Maximization algorithms, and Bayesian estimation. The described ancestral state reconstruction algorithm is implemented in the Rphylopars functions anc.recon and phylopars.

References Boettiger, C., & Ralph, P. (2012). Is your phylogeny informative? Measuring the power of comparative methods. Evolution, 66, 2240–2251. Bruggeman, J., Heringa, J., & Brandt, B. W. (2009). PhyloPars: Estimation of missing parameter values using phylogeny. Nucleic Acids Research, 37, W179–W18. Elliot, M. J. (2015). Identical inferences about correlated evolution arise from ancestral state reconstruction and independent contrasts. Journal of Theoretical Biology, 364, 321–325. Felsenstein, J. (1985). Phylogenies and the comparative method. American Naturalist, 125, 1–15. Felsenstein, J. (2004). Brownian motion and gene frequencies. In Inferring phylogenies (pp. 391–414). Sunderland, MA: Sinauer Associates. Felsenstein, J. (2008). Comparative methods with sampling error and within-species variation: Contrasts revisited and revised. American Naturalist, 171, 713–725. FitzJohn, R. J. (2012). Diversitree: Comparative phylogenetic analyses of diversification in R. Methods in Ecology & Evolution, 3, 1084–1092. Freckleton, R. P. (2012). Fast likelihood calculations for comparative analyses. Methods in Ecology & Evolution, 3, 940–947. Garland, T., & Ives, A. R. (2000). Using the past to predict the present: Confidence intervals for regression equations in phylogenetic comparative methods. American Naturalist, 155, 346–364. Garland, T., Midford, P. E., & Ives, A. R. (1999). An introduction to phylogenetically based statistical methods, with a new method for confidence intervals on ancestral values. American Zoologist, 39, 374–388. Goolsby, E. W. (2016). Likelihood-based parameter estimation for high-dimensional phylogenetic comparative models: Overcoming the limitations of ‘distance-based’ methods. Systematic Biology, 65, 852–870. Goolsby, E. W., Bruggeman, J., & Ané, C. (2017). Rphylopars: Fast multivariate phylogenetic comparative methods for missing data and within-species variation. Methods in Ecology and Evolution, 8, 22–27. Hadfield, J. D., & Nakagawa, S. (2010). General quantitative genetic methods for comparative biology: Phylogenies, taxonomies and multi-trait models for continuous and categorical characters. Journal of Evolutionary Biology, 23, 494–508. Ho, L. T. H., & Ané, C. (2014). A linear-time algorithm for Gaussian and non-Gaussian trait evolution models. Systematic Biology, 63, 397–408. Ives, A. R., Midford, P. E., & Garland, T. Jr (2007). Within-species variation and measurement error in phylogenetic comparative methods. Systematic Biology, 56, 252–270. Maddison, W. P. (1991). Squared-change parsimony reconstructions of ancestral states for continuous-valued characters on a phylogenetic tree. Systematic Zoology, 40, 304–314. Martins, E. P., & Hansen, T. F. (1997). Phylogenies and the comparative method: A general approach to incorporating phylogenetic information into the analysis of interspecific data. American Naturalist, 149, 646–667. Paradis, E., Claude, J., & Strimmer, K. (2004). APE: Analyses of phylogenetics and evolution in R language. Bioinformatics, 20, 289–290. Revell, L. J. (2012). phytools: An R package for phylogenetic comparative biology (and other things). Methods in Ecology & Evolution, 3, 217–223. Revell, L. J., & Reynolds, G. (2012). A new Bayesian method for fitting evolutionary models to comparative data with intraspecific variation. Evolution, 66, 2697–2707. Rohlf, F. J. (2001). Comparative methods for the analysis of continuous variables: Geometric interpretations. Evolution, 55, 2143–2160. Schluter, D., Price, T., Moores, A. O., & Ludwig, D. (1997). Likelihood of ancestral states in adaptive radiation. Evolution, 51, 1699–1711. Swofford, D. L., & Maddison, W. P. (1987). Reconstructing ancestral character states under Wagner parsimony. Mathematical Biosciences, 87, 199–229.