论文标题
测试树木与内部标签的协议
Testing the Agreement of Trees with Internal Labels
论文作者
论文摘要
协议问题的输入是$ p = \ {t_1，t_2，\ dots，t_k \} $的系统发育树（称为输入树），在部分重叠的类群集上。问题是是否存在一个树$ t $，称为协议树，其分类群集是输入树的分类单元组的结合，因此，对于每个$ i \ in \ {1，2，\ dots，k \} $，$ t $限制了$ t_i $ $ t_i $的$ t $的限制。我们给出了$ o（n k（\ sum_ {i \ in [k]} d_i + \ log^2（nk）））$算法，用于对协议问题的概括，其中输入树具有内部标签，其中$ n $是$ p $ in $ p $ n $ p $ p $ p $ p $ d_ d_ d_ d_ d_ d_ is p $ d_ is p $ d_ is p $ d_ is p $ d_ is p $ d_ is的$ d_ is p $ d_ is p $ d_ is p $ d_ is p $ d_ is p $ d_ is p $ d_ is a n y is $ d_ is的数量的最大数量。
The input to the agreement problem is a collection $P = \{T_1, T_2, \dots , T_k\}$ of phylogenetic trees, called input trees, over partially overlapping sets of taxa. The question is whether there exists a tree $T$, called an agreement tree, whose taxon set is the union of the taxon sets of the input trees, such that for each $i \in \{1, 2, \dots , k\}$, the restriction of $T$ to the taxon set of $T_i$ is isomorphic to $T_i$. We give a $O(n k (\sum_{i \in [k]} d_i + \log^2(nk)))$ algorithm for a generalization of the agreement problem in which the input trees may have internal labels, where $n$ is the total number of distinct taxa in $P$, $k$ is the number of trees in $P$, and $d_i$ is the maximum number of children of a node in $T_i$.
