An adjacent-swap Markov chain on coalescent trees

DOI10.1017/JPR.2022.15zbMATH Open1501.60038arXiv2012.08030OpenAlexW3111197559WikidataQ114118001 ScholiaQ114118001MaRDI QIDQ5049907FDOQ5049907

Authors: Mackenzie Simper, Julia A. Palacios 

Publication date: 14 November 2022

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)