An adjacent-swap Markov chain on coalescent trees. (2nd December 2022)

• Record Type: Journal Article
• Authors: Simper, Mackenzie; Palacios, Julia A.
• Is Part Of: Journal of applied probability. Volume 59:Number 4(2022)
• Page Start: 1243
• Page End: 1260
• Publication Date: 2022-12-02
• Subjects: Random transpositions -- lumped Markov chain -- Tajima distribution; 60J10 -- 60J90; 519.2
• DOI: 10.1017/jpr.2022.15
• Languages: English
• ISSNs: 0021-9002

Abstract

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 a 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.