A Linear-Time Algorithm for Gaussian and Non-Gaussian Trait Evolution Models

We developed a linear-time algorithm applicable to a large class of trait evolution models, for efficient likelihood calculations and parameter inference on very large trees. Our algorithm solves the traditional computational burden associated with two key terms, namely the determinant of the phylogenetic covariance matrix V and quadratic products involving the inverse of V. Applications include Gaussian models such as Brownian motion-derived models like Pagel's lambda, kappa, delta, and the early-burst model; Ornstein-Uhlenbeck models to account for natural selection with possibly varying selection parameters along the tree; as well as non-Gaussian models such as phylogenetic logistic regression, phylogenetic…

• NS
  National Science Foundation

  Awards: DMS-1106483, 0949121, 1106483
• NI
  National Institute for Mathematical and Biological Synthesis