License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.20
URN: urn:nbn:de:0030-drops-57218
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5721/
Go to the corresponding LIPIcs Volume Portal

Bodirsky, Manuel ; Jonsson, Peter ; Van Pham, Trung

The Complexity of Phylogeny Constraint Satisfaction

pdf-format:
21.pdf (0.6 MB)

Abstract

We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains for example the rooted triple consistency problem, forbidden subtree problems, the quartet consistency problem, and many other problems studied in the bioinformatics literature. The studied problems can be described as constraint satisfaction problems where the constraints have a first-order definition over the rooted triple relation. We show that every such phylogeny problem can be solved in polynomial time or is NP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithm of Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithm repeatedly solves linear equation systems to construct a solution in polynomial time. We then show that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Our classification establishes a dichotomy for a large class of infinite structures that we believe is of independent interest in universal algebra, model theory, and topology. The proof of our main result combines results and techniques from various research areas: a recent classification of the model-complete cores of the reducts of the homogeneous binary branching C-relation, Leeb’s Ramsey theorem for rooted trees, and universal algebra.

BibTeX - Entry

@InProceedings{bodirsky_et_al:LIPIcs:2016:5721,
  author =	{Manuel Bodirsky and Peter Jonsson and Trung Van Pham},
  title =	{{The Complexity of Phylogeny Constraint Satisfaction}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5721},
  URN =		{urn:nbn:de:0030-drops-57218},
  doi =		{10.4230/LIPIcs.STACS.2016.20},
  annote =	{Keywords: constraint satisfaction problems, computational complexity, phylogenetic reconstruction, ramsey theory, model theory}
}

Keywords: constraint satisfaction problems, computational complexity, phylogenetic reconstruction, ramsey theory, model theory
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI