Phylogenetic Stochastic Mapping Without Matrix Exponentiation

• Activity Number: 453
• Type: Contributed
• Date/Time: Wednesday, August 6, 2014 : 8:30 AM to 10:20 AM
• Sponsor: WNAR
• Author(s): Jan Irvahn*+ and Vladimir Minin
• Companies: and University of Washington
• Keywords: phylogenetic ; stochastic ; mapping ; Markov ; uniformization

Abstract

Phylogenetic stochastic mapping is a method for reconstructing the history of trait changes on a phylogenetic tree relating organisms carrying the trait. State-of-the-art methods assume that a 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 because they exponentiate CTMC infinitesimal rate matrices, an operation whose computational complexity grows as the size of the CTMC state space cubed. We introduce a new approach, based on a CTMC technique called uniformization, that does not use matrix exponentiation. Our method is based on a Markov chain Monte Carlo algorithm that targets the distribution of trait histories conditional on observed trait data. The complexity of our method grows as the size of the CTMC state space squared. We show that even on moderately large state spaces (amino acids, codons) our MCMC method can be faster than currently used matrix exponentiation methods. This finding is important, because these state spaces are ubiquitous in molecular evolution studies, but when dealing with large datasets, state-of-the-art methods often grind to a halt.