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

TLDR

The authors present a linear‑time algorithm for efficient likelihood calculation and parameter inference across a broad class of trait evolution models on very large phylogenetic trees. The algorithm reduces the computational bottleneck of determinant and quadratic terms by exploiting a 3‑point covariance structure, enabling efficient analysis of Gaussian and non‑Gaussian evolutionary models—including Brownian motion, OU, logistic, Poisson, GLMM—and related phylogenetic methods, and is available in the R package phylolm. The method dramatically speeds up analyses, allowing complex models and large‑scale resampling on extensive trees, and reveals that the 3‑point covariance structure uniquely defines a rooted tree whose branch lengths parameterize the trait covariance matrix.

Abstract

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 Poisson regression, and phylogenetic generalized linear mixed models. Outside of phylogenetic regression, our algorithm also applies to phylogenetic principal component analysis, phylogenetic discriminant analysis or phylogenetic prediction. The computational gain opens up new avenues for complex models or extensive resampling procedures on very large trees. We identify the class of models that our algorithm can handle as all models whose covariance matrix has a 3-point structure. We further show that this structure uniquely identifies a rooted tree whose branch lengths parametrize the trait covariance matrix, which acts as a similarity matrix. The new algorithm is implemented in the R package phylolm, including functions for phylogenetic linear regression and phylogenetic logistic regression.