An adjacent-swap Markov chain on coalescent trees

DOI10.1017/JPR.2022.15MaRDI QIDQ5049907zbMATH OpenOpenAlexWikidataFDO

Authors Mackenzie Simper, Julia A. Palacios

Publication date 14 November 2022

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.08030

zbMATH Keywords

random transpositionslumped Markov chainTajima distribution

Mathematics Subject Classification ID

Bayesian inference (62F15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coalescent processes (60J90)

Abstract: The standard coalescent is widely used in evolutionary biology and population genetics to model the ancestral history of a sample of molecular sequences as a rooted and ranked binary tree. In this paper, we present a representation of the space of ranked trees as a space of constrained ordered matched pairs. We use this representation to define ergodic Markov chains on labeled and unlabeled ranked tree shapes analogously to transposition chains on the space of permutations. We show that an adjacent-swap chain on labeled and unlabeled ranked tree shapes has mixing time at least of order $n^3$, and at most of order $n^4$. Bayesian inference methods rely on Markov chain Monte Carlo methods on the space of trees. Thus, it is important to define good Markov chains which are easy to simulate and for which rates of convergence can be studied.

Recommendations

• The coalescent tree of a Markov branching process with generalised logistic growth
• Random recursive trees and the Bolthausen-Sznitman coalescent
• A representation for exchangeable coalescent trees and generalized tree-valued Fleming-Viot processes
• A Markov chain model of coalescence with recombination
• The coalescent structure of continuous-time Galton-Watson trees
• Markov jump processes in modeling coalescent with recombination
• On the link between Markovian trees and tree-structured Markov chains
• Beta-coalescents and continuous stable random trees
• Mixing Time for a Markov Chain on Cladograms
• Recursions for the exchangeable partition function of the seedbank coalescent

Cites work

• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1750693 (Why is no real title available?)
• A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
• Alternating permutations and binary increasing trees
• Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species
• Finding the best resolution for the Kingman-Tajima coalescent: theory and applications
• Increasing trees and alternating permutations
• Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Matchings and phylogenetic trees
• Mixing Time for a Markov Chain on Cladograms
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Mixing times of lozenge tiling and card shuffling Markov chains
• On the total external length of the Kingman coalescent
• Random doubly stochastic tridiagonal matrices
• Random walks on trees and matchings
• Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting
• Shuffling chromosomes
• The coalescent

Cited in

(3)

• A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
• An Efficient Coalescent Model for Heterochronously Sampled Molecular Data
• scientific article; zbMATH DE number 1750693 (Why is no real title available?)

Describes a project that uses

Uses Software

• BEAST
• BEAUti

This page was built for publication: An adjacent-swap Markov chain on coalescent trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5049907)