论文标题
在理论和实践中检查系统发育的决定性
Checking Phylogenetic Decisiveness in Theory and in Practice
论文作者
论文摘要
假设我们有一个由$ n $ n $ taxa组成的$ x $，我们获得了$ k $ loci的信息，从中为$ x $构建系统发育。每个基因座仅提供一小部分分类单元的信息。问题是这些数据是否足以构建可靠的系统发育。决定性问题以组合表示了这个问题。尽管已知的确切表征是确定性的，但问题的复杂性是开放的。在这里，我们将果断性与超图着色问题联系起来。 We use this idea to (1) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (2) devise an exact algorithm for decisiveness, (3) develop problem reduction rules, and use them to obtain efficient algorithms for inputs with few loci, and (4) devise an integer linear programming formulation of the decisiveness problem, which allows us to analyze data sets that arise in practice.
Suppose we have a set $X$ consisting of $n$ taxa and we are given information from $k$ loci from which to construct a phylogeny for $X$. Each locus offers information for only a fraction of the taxa. The question is whether this data suffices to construct a reliable phylogeny. The decisiveness problem expresses this question combinatorially. Although a precise characterization of decisiveness is known, the complexity of the problem is open. Here we relate decisiveness to a hypergraph coloring problem. We use this idea to (1) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (2) devise an exact algorithm for decisiveness, (3) develop problem reduction rules, and use them to obtain efficient algorithms for inputs with few loci, and (4) devise an integer linear programming formulation of the decisiveness problem, which allows us to analyze data sets that arise in practice.
