A linear-time algorithm for Gaussian and non-Gaussian trait evolution models.

Area of Science:

• Evolutionary biology
• Computational biology
• Phylogenetics

Background:

• Trait evolution models on large phylogenetic trees face computational challenges.
• Calculating determinants and inverses of phylogenetic covariance matrices is computationally intensive.
• Existing methods struggle with the scale of modern phylogenetic datasets.

Purpose of the Study:

• To develop a linear-time algorithm for efficient likelihood calculations and parameter inference in trait evolution models.
• To address the computational bottleneck of determinant and inverse calculations for phylogenetic covariance matrices.
• To enable the application of complex evolutionary models to very large phylogenetic trees.

Main Methods:

• Developed a linear-time algorithm applicable to models with a 3-point covariance matrix structure.
• Algorithm efficiently computes the determinant and inverse of the phylogenetic covariance matrix (V).
• Implemented the algorithm in the R package 'phylolm' for phylogenetic regression models.

Main Results:

• The algorithm significantly reduces computational burden for likelihood calculations and parameter inference.
• Successfully applied to Gaussian (e.g., Brownian motion, Ornstein-Uhlenbeck) and non-Gaussian models (e.g., phylogenetic logistic regression).
• Demonstrated applicability to phylogenetic principal component analysis, discriminant analysis, and prediction.

Conclusions:

• The new algorithm provides a computational breakthrough for analyzing trait evolution on large phylogenies.
• Enables new avenues for complex models and resampling procedures on extensive datasets.
• The 'phylolm' R package offers practical tools for researchers using these advanced phylogenetic methods.