Phylogenetic stochastic mapping without matrix exponentiation.

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Biology

Background:

• Phylogenetic stochastic mapping reconstructs trait evolution history on phylogenetic trees.
• Current methods use continuous-time Markov chains (CTMC) but are computationally intensive for large state spaces due to matrix exponentiation (O(n^3)).

Purpose of the Study:

• Introduce a novel, computationally efficient method for phylogenetic stochastic mapping.
• Develop an algorithm that scales better with increasing trait state space size.

Main Methods:

• Developed a new Markov chain Monte Carlo (MCMC) algorithm utilizing CTMC uniformization, avoiding matrix exponentiation.
• The MCMC algorithm targets trait histories conditional on observed tip data.
• Algorithm complexity scales quadratically with state space size (O(n^2)) and can leverage matrix sparsity.

Main Results:

• The new MCMC method demonstrates significant speed advantages over matrix exponentiation, especially for larger state spaces.
• Even for the moderately large codon state space, the MCMC approach is considerably faster.
• The computational efficiency gain is more pronounced when the rate matrix is sparse.

Conclusions:

• The uniformization-based MCMC algorithm offers a more efficient alternative for phylogenetic stochastic mapping with large state spaces.
• This method significantly reduces computational burden, enabling more complex evolutionary analyses.
• The approach is particularly beneficial in scenarios involving large trait state spaces, such as codon evolution.