  Phylogenetic stochastic mapping is a method for reconstructing the history of
trait changes on a phylogenetic tree relating species/organisms carrying the
trait. State-of-the-art methods assume that the trait evolves according to a
continuous-time Markov chain (CTMC) and work well for small state spaces. The
computations slow down considerably for larger state spaces (e.g. space of
codons), because current methodology relies on exponentiating CTMC
infinitesimal rate matrices -- an operation whose computational complexity
grows as the size of the CTMC state space cubed. In this work, we introduce a
new approach, based on a CTMC technique called uniformization, that does not
use matrix exponentiation for phylogenetic stochastic mapping. Our method is
based on a new Markov chain Monte Carlo (MCMC) algorithm that targets the
distribution of trait histories conditional on the trait data observed at the
tips of the tree. The computational complexity of our MCMC method grows as the
size of the CTMC state space squared. Moreover, in contrast to competing matrix
exponentiation methods, if the rate matrix is sparse, we can leverage this
sparsity and increase the computational efficiency of our algorithm further.
Using simulated data, we illustrate advantages of our MCMC algorithm and
investigate how large the state space needs to be for our method to outperform
matrix exponentiation approaches. We show that even on the moderately large
state space of codons our MCMC method can be significantly faster than
currently used matrix exponentiation methods.
