Dataset Information

Phylogenetic stochastic mapping without matrix exponentiation.

ABSTRACT: Phylogenetic stochastic mapping is a method for reconstructing the history of trait changes on a phylogenetic tree relating species/organism carrying the trait. State-of-the-art methods assume that the trait evolves according to a continuous-time Markov chain (CTMC) and works 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, which 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.

SUBMITTER: Irvahn J

PROVIDER: S-EPMC4148059 | biostudies-literature | 2014 Sep

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Phylogenetic stochastic mapping without matrix exponentiation.

Irvahn Jan J Minin Vladimir N VN

Journal of computational biology : a journal of computational molecular cell biology 20140611 9

Phylogenetic stochastic mapping is a method for reconstructing the history of trait changes on a phylogenetic tree relating species/organism carrying the trait. State-of-the-art methods assume that the trait evolves according to a continuous-time Markov chain (CTMC) and works 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 ...[more]

PMID: 24918812

Similar Datasets

Project description:Increasing evidence has emerged for non-random spatial distributions of microbes, but knowledge of the processes that cause variation in microbial assemblage among ecosystems is lacking. For instance, some studies showed that deterministic processes such as habitat specialization are important, while other studies hold that bacterial communities are assembled by stochastic forces. Here we examine the relative influence of deterministic and stochastic processes for bacterial communities from subsurface environments, stream biofilm, lake water, lake sediment and soil using pyrosequencing of the 16S ribosomal RNA gene. We show that there is a general pattern in phylogenetic signal in species ecological niches across recent evolutionary time for all studied habitats, enabling us to infer the influences of community assembly processes from patterns of phylogenetic turnover in community composition. The phylogenetic dissimilarities among-habitat types were significantly higher than within them, and the communities were clustered according to their original habitat types. For communities within-habitat types, the highest phylogenetic turnover rate through space was observed in subsurface environments, followed by stream biofilm on mountainsides, whereas the sediment assemblages across regional scales showed the lowest turnover rate. Quantifying phylogenetic turnover as the deviation from a null expectation suggested that measured environmental variables imposed strong selection on bacterial communities for nearly all sample groups. For three sample groups, spatial distance reflected unmeasured environmental variables that impose selection, as opposed to spatial isolation. Such characterization of spatial and environmental variables proved essential for proper interpretation of partial Mantel results based on observed beta diversity metrics. In summary, our results clearly indicate a dominant role of deterministic processes on bacterial assemblages and highlight that bacteria show strong habitat associations that have likely emerged through evolutionary adaptation.

Dataset Information

Phylogenetic stochastic mapping without matrix exponentiation.

Publications

Phylogenetic stochastic mapping without matrix exponentiation.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets