Phylogenetic decisiveness and no-rainbow hypergraph coloring
Suppose we aim to build a phylogeny for a set of taxa X using information from a collection of loci, where each locus offers information for only a fraction of the taxa. The question is whether, based solely on the pattern of data availability, called a taxon coverage pattern, one can determine if the data suffices to construct a reliable phylogeny. The decisiveness problem expresses this question combinatorially. Informally, a taxon coverage pattern is decisive if the following holds for any binary phylogenetic tree T for X: the collection of phylogenetic trees obtained by restricting T to the subset of X covered by each locus uniquely determines T. The decisiveness problem is the problem of determining whether a given coverage pattern is decisive. Here we relate the decisiveness problem to a hypergraph coloring problem. We use this connection to (1) show that the decisiveness problem is co-NP complete, (2) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (3) devise an exact algorithm for decisiveness, (4) develop problem reduction rules, and use them to obtain efficient algorithms for inputs with few loci, (5) apply local search and devise a deterministic and a randomized algorithm for decisiveness(6) devise Boolean satisfiability (SAT) and integer linear programming formulations (ILP) of decisiveness, which allow us to analyze data sets that arise in practice. For data sets that are not decisive, we use our SAT and ILP formulations to obtain decisive subsets of the data.