Gradients Do Grow on Trees: A Linear-Time O(N)-Dimensional Gradient for Statistical Phylogenetics.

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Calculating log-likelihood and its gradient is computationally intensive for phylogenetic algorithms.
• Standard gradient calculations scale quadratically (O(N^2)) with the number of sequences (N).
• High-throughput sequencing generates large datasets, challenging existing phylogenetic methods.

Purpose of the Study:

• To develop a computationally efficient algorithm for gradient evaluation in phylogenetic analysis.
• To enable tractable phylogenetic reconstruction for large molecular sequence datasets.
• To infer branch-specific evolutionary rates for pathogenic viruses.

Main Methods:

• Developed a linear-time (O(N)) algorithm for gradient evaluation.
• Applied the algorithm to general continuous-time Markov processes on phylogenetic trees.
• Did not assume stationarity or reversibility for the substitution models.

Main Results:

• Achieved significant improvements in inference efficiency for phylogenetic analyses.
• Demonstrated 126- to 234-fold speedup in maximum-likelihood optimization.
• Showed a 16- to 33-fold computational performance increase within a Bayesian framework.

Conclusions:

• The new linear-time algorithm makes large-scale phylogenetic analyses computationally feasible.
• Efficient gradient evaluation facilitates accurate inference of evolutionary rates for viruses like West Nile, Dengue, and Lassa.
• This advancement supports the analysis of increasingly large molecular sequence datasets in evolutionary biology.