标题： 与完美进化树相容的二叉树枚举 显示英文标题

标题： Enumeration of binary trees compatible with a perfect phylogeny

摘要： 用于描述分子序列变异的进化模型假设，在非重组基因组片段中，序列共享可以表示为系谱的祖先——一个根节点、二叉、带时间的树，末端对应于单个序列。 在无限位点突变模型下，突变随机地叠加在系谱的分支上，使得每个突变发生在之前未发生突变的染色体位置；如果突变发生在内部分支上，则从该分支衍生的所有个体都携带该突变。 这意味着，从该模型中观察到的分子变异模式会对系谱的隐藏状态空间施加组合约束。 特别是，观察到的分子变异可以表示为完美系统发育树的形式，这是一种完全编码序列之间突变差异的树结构。 对于n个序列的样本，完美系统发育树可能不具有n个不同的叶节点，因此可能与许多可能的二叉树结构相容，这些结构可以描述n个序列之间的进化关系。 在此，我们研究与完美系统发育树相容的二叉排序和无排序树形状的枚举性质，因此，也研究在无限位点突变模型下，给定观察到的突变模式时，二叉排序和无排序树形状的条件。 我们提供了这些形状的递归枚举。 我们考虑既可以表示为二叉也可以是多分叉的完美系统发育树。 这些结果对分子序列集合所依赖的进化参数的统计推断的计算方面具有影响。 显示英文摘要

摘要： Evolutionary models used for describing molecular sequence variation suppose that at a non-recombining genomic segment, sequences share ancestry that can be represented as a genealogy--a rooted, binary, timed tree, with tips corresponding to individual sequences. Under the infinitely-many-sites mutation model, mutations are randomly superimposed along the branches of the genealogy, so that every mutation occurs at a chromosomal site that has not previously mutated; if a mutation occurs at an interior branch, then all individuals descending from that branch carry the mutation. The implication is that observed patterns of molecular variation from this model impose combinatorial constraints on the hidden state space of genealogies. In particular, observed molecular variation can be represented in the form of a perfect phylogeny, a tree structure that fully encodes the mutational differences among sequences. For a sample of n sequences, a perfect phylogeny might not possess n distinct leaves, and hence might be compatible with many possible binary tree structures that could describe the evolutionary relationships among the n sequences. Here, we investigate enumerative properties of the set of binary ranked and unranked tree shapes that are compatible with a perfect phylogeny, and hence, the binary ranked and unranked tree shapes conditioned on an observed pattern of mutations under the infinitely-many-sites mutation model. We provide a recursive enumeration of these shapes. We consider both perfect phylogenies that can be represented as binary and those that are multifurcating. The results have implications for computational aspects of the statistical inference of evolutionary parameters that underlie sets of molecular sequences.