Rapid likelihood analysis on large phylogenies using partial sampling of substitution histories

Area of Science:

• Computational Biology
• Molecular Evolution
• Bioinformatics

Background:

• Large comparative genomic datasets offer unprecedented opportunities for understanding molecular evolution.
• Analyzing these datasets presents significant computational challenges for traditional likelihood-based methods.
• Markov chain Monte Carlo (MCMC) methods augmenting substitution histories show promise for computational efficiency.

Purpose of the Study:

• To analyze the computational costs of likelihood-based evolutionary reconstruction methods.
• To develop a theoretical framework for identifying computational bottlenecks.
• To introduce a novel, computationally efficient method for analyzing large genomic datasets.

Main Methods:

• Developed a theoretical framework to analyze computational costs based on model and data set complexity.
• Combined novel variations of the conditional pathway integration approach with existing advances.
• Introduced a "partial sampling" technique for substitution histories.

Main Results:

• The partial sampling method is significantly faster and scales better with model complexity and data set size compared to existing approaches.
• On mammalian cytochrome-b sequences, partial sampling was 10x faster than PhyloBayes and 100x faster than fully integrated histories for nucleotide models.
• For amino acid substitution models, partial sampling was 1,600x faster than fully integrated histories, demonstrating superior scaling.

Conclusions:

• Partial sampling of substitution histories dramatically improves the efficiency of likelihood approaches for large-scale evolutionary analyses.
• The new method is accurate, simple to implement, and offers substantial computational savings.
• This technique enhances the utility of phylogenetic reconstruction for complex evolutionary processes.