从 Least Common Ancestors 推断 DAG 和 Phylogenetic 网络
定向鰰凹图(DAG)中两片叶子的最不共同的祖先(LCA)是一个顶点,它是两片叶子的祖先,没有适当的后代,也是它们共同的祖先。 LCA在根树中捕获等级关系,更普遍的是DAGs。 1981年,Aho等人介绍了一个问题,即确定一组对X的LCA约束,即i,j)<(k,l)与i,j,k,l∈X的形式(i,j),k,l∈X,是否可以通过根树来实现,其叶子集为X,因此,每当(i,j)<(k,l),i,j的LCA是k,l的后代。 他们还提出了一个多项式时间算法BUILD来解决这个问题。 然而,许多这样的约束系统不能被任何树实现,这引发了一个问题,即它们是否可以被更普遍的DAG实现。 我们将Aho等人的框架从树扩展到DAG,为在这个更广泛的环境中推理LCA约束提供了理论和算法基础。 给定LCA约束的集合R,我们定义其+关闭R^+,捕获R所暗示的额外LCA关系。 使用R^+,我们构造一个规范的DAG G_R,并证明R是DAG可实现的,只有当它由G_R实现。 我们进一步将这种构造适应系统发育网络,定义规范网络 N_R 并证明它是常规的,即它与其底层集系统的 Hasse 图相吻合。 最后,我们表明,对于任何可实现 DAG 的 R ,它的经典闭包——包括每个 DAG 实现 R 的所有 LCA 约束——都与其 + 闭合相吻合。 所有构造在多项式时间都是可计算的,我们为每个构造提供显式算法。
组合数学离散数学
