2011/01/11 by Maria Luisa Bonet, Marı́a Luisa Bonet, Bonet, Maria Luisa +4
Biochemistry, Genetics and Molecular Biology · Computer Science · #Biomedical Text Mining and Ontologies #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #cs.CC #cs.DS #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1101.2170
25 pages, 7 figures
arxiv created 2011/03/28 · arxiv updated 2015/03/17
We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of Betweenness, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that Quartet Compatibility, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel's \sc Quartet Challenge, which asks whether a solution to Quartet Compatibility is unique, is coNP-complete.