Himwich Zoe M, Rosenberg Noah A
Department of Mathematics, Stanford University, Stanford, CA 94305 USA.
Department of Biology, Stanford University, Stanford, CA 94305 USA.
Adv Appl Math. 2020 Feb;113. doi: 10.1016/j.aam.2019.101939. Epub 2019 Oct 31.
Given a gene tree topology and a species tree topology, a coalescent history represents a possible mapping of the list of gene tree coalescences to associated branches of a species tree on which those coalescences take place. Enumerative properties of coalescent histories have been of interest in the analysis of relationships between gene trees and species trees. The simplest enumerative result identifies a bijection between coalescent histories for a matching caterpillar gene tree and species tree with monotonic paths that do not cross the diagonal of a square lattice, establishing that the associated number of coalescent histories for -taxon matching caterpillar trees ( ⩾ 2) is the Catalan number . Here, we show that a similar bijection applies for caterpillars, connecting coalescent histories for a non-matching caterpillar gene tree and species tree to a class of monotonic paths. The result provides a simplified algorithm for enumerating coalescent histories in the non-matching caterpillar case. It enables a rapid proof of a known result that given a caterpillar species tree, no non-matching caterpillar gene tree has a number of coalescent histories exceeding that of the matching gene tree. Additional results on coalescent histories can be obtained by a bijection between permissible roadblocked monotonic paths and Dyck paths. We study the number of coalescent histories for non-matching caterpillar gene trees that differ from the species tree by nearest-neighbor-interchange and subtree-prune-and-regraft moves, characterizing the non-matching caterpillar with the largest number of coalescent histories. We discuss the implications of the results for the study of the combinatorics of gene trees and species trees.
给定一个基因树拓扑结构和一个物种树拓扑结构，一个合并历史表示基因树合并列表到物种树相关分支的一种可能映射，在这些物种树分支上发生那些合并。合并历史的枚举性质在基因树与物种树关系的分析中备受关注。最简单的枚举结果确定了匹配的毛毛虫基因树和物种树的合并历史与不穿过正方形晶格对角线的单调路径之间的双射，从而确定了(n)分类单元匹配毛毛虫树（(n\geqslant2)）的相关合并历史数量是卡特兰数(C_n)。在此，我们表明类似的双射适用于毛毛虫，将不匹配的毛毛虫基因树和物种树的合并历史与一类(n)单调路径联系起来。该结果为枚举不匹配毛毛虫情况下的合并历史提供了一种简化算法。它使得能够快速证明一个已知结果，即给定一个毛毛虫物种树，没有不匹配的毛毛虫基因树的合并历史数量超过匹配基因树的合并历史数量。通过允许的受阻单调路径与戴克路径之间的双射，可以获得关于合并历史的其他结果。我们研究了通过最近邻交换和子树修剪与重新嫁接移动与物种树不同的不匹配毛毛虫基因树的合并历史数量，刻画了具有最大合并历史数量的不匹配毛毛虫。我们讨论了这些结果对基因树和物种树组合学研究的影响。
