Phylogenetic Decisiveness and No-Rainbow Coloring
Missing data poses a challenge to assembling phylogenetic trees. The question we address here is how much data can we afford to miss without compromising accuracy. We focus on data sets assembled by concatenating data from many (sometimes thousands) of loci. 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. A precise characterization of decisiveness is known, and it has proven that the problem is Np-Complete.
Decisiveness is related to the no-rainbow coloring problem in hypergraphs. Assume we have a hypergraph H = (X, E) with n nodes and |E| hyperedges, and we want to use precisely r colors to color the nodes in H while avoiding a rainbow coloring.
In this presentation, we show new deterministic and randomized algorithms. We use local search and covering codes to design the new algorithms. The algorithms we present are faster than the existing algorithms.
Committee: David Fernandez-Baca (major professor), Pavan Aduri, Oliver Eulenstein, Giora Slutzki, and Ryan Martin
Location: Zoom https://iastate.zoom.us/j/96351309680?pwd=NC9ranlxOHRiN29BN2dlTTJOTHdVQT09