Disanto Filippo, Rosenberg Noah A
Department of Biology, Stanford University , Stanford, California.
J Comput Biol. 2015 Oct;22(10):918-29. doi: 10.1089/cmb.2015.0015. Epub 2015 May 14.
Coalescent histories are combinatorial structures that describe for a given gene tree and species tree the possible lists of branches of the species tree on which the gene tree coalescences take place. Properties of the number of coalescent histories for gene trees and species trees affect a variety of probabilistic calculations in mathematical phylogenetics. Exact and asymptotic evaluations of the number of coalescent histories, however, are known only in a limited number of cases. Here we introduce a particular family of species trees, the lodgepole species trees (λn)n ≥ 0, in which tree λn has m = 2n+1 taxa. We determine the number of coalescent histories for the lodgepole species trees, in the case that the gene tree matches the species tree, showing that this number grows with m!! in the number of taxa m. This computation demonstrates the existence of tree families in which the growth in the number of coalescent histories is faster than exponential. Further, it provides a substantial improvement on the lower bound for the ratio of the largest number of matching coalescent histories to the smallest number of matching coalescent histories for trees with m taxa, increasing a previous bound of [Formula: see text] to [Formula: see text]. We discuss the implications of our enumerative results for phylogenetic computations.
合并历史是一种组合结构，它针对给定的基因树和物种树描述了基因树发生合并的物种树分支的可能列表。基因树和物种树的合并历史数量的性质影响着数学系统发育学中的各种概率计算。然而，合并历史数量的精确和渐近评估仅在有限的情况下已知。在这里，我们引入了一个特定的物种树家族，即黑松物种树（λn）n≥0，其中树λn有m = 2n + 1个分类单元。我们确定了基因树与物种树匹配情况下黑松物种树的合并历史数量，表明这个数量随着分类单元数量m以m!!的速度增长。这个计算证明了存在这样的树家族，其中合并历史数量的增长速度快于指数增长。此外，它显著改进了具有m个分类单元的树中最大匹配合并历史数量与最小匹配合并历史数量之比的下限，将先前的下限[公式：见正文]提高到了[公式：见正文]。我们讨论了我们的枚举结果对系统发育计算的影响。
