论文标题
在融合树上的相邻Swap Markov链
An adjacent-swap Markov chain on coalescent trees
论文作者
论文摘要
标准结合被广泛用于进化生物学和种群遗传学，以模拟分子序列样本的祖先历史，作为根和排名的二元树。在本文中，我们介绍了排名树的空间作为约束有序匹配对的空间。我们使用此表示形式在标记和未标记的排名树形状上定义了Ergodic Markov链，类似于排列空间上的换座链。我们表明，在标记和未标记的排名树形状上的相邻链条链具有至少订单$ n^3 $的时间，并且在大多数顺序$ n^{4} $中。贝叶斯推论方法依赖于马尔可夫链在树木空间上的蒙特卡洛方法。因此，定义易于模拟的良好马尔可夫链很重要，并且可以研究收敛速度。
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.
