Uniformization for sampling realizations of Markov processes: Applications to Bayesian implementations of codon substitution models

Motivation: Mapping character state changes over phylogenetic trees is central to the study of evolution. However, current probabi-listic methods for generating such mappings are ill-suited to certain types of evolutionary models, in particular, the widely used models of codon substitution. Results: We describe a general method, based on a uniformization technique, which can be utilized to generate realizations of a Mar-kovian substitution process conditional on an alignment of character states and a given tree topology. The method is applicable under a wide range of evolutionary models, and to illustrate its usefulness in practice, we embed it within a data augmentation-based Markov chain Monte Carlo sampler, for approximating posterior distributions under previously proposed codon substitution models. The sampler is found to be more efcient than the conventional pruning-based sampler, with decorrelation times between draws from the posterior reduced by a factor of twenty or more. Contact