Phylogenetic decisiveness and no-rainbow hypergraph coloring

Date
2021-01-01
Authors
Parvini, Ghazaleh
Major Professor
Advisor
David Fernandez-Baca
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer Science
Abstract

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.

Comments
Description
Keywords
Citation
Source