Document Open Access Logo

The Complexity of Phylogeny Constraint Satisfaction

Authors Manuel Bodirsky, Peter Jonsson, Trung Van Pham

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.20.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Manuel Bodirsky
Peter Jonsson
Trung Van Pham

Cite As Get BibTex

Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.20

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.

Subject Classification

Keywords
  • constraint satisfaction problems
  • computational complexity
  • phylogenetic reconstruction
  • ramsey theory
  • model theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, and Jeffrey D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10(3):405-421, 1981. Google Scholar
  2. Manuel Bodirsky. Cores of countably categorical structures. Logical Methods in Computer Science, 3(1):1-16, 2007. Google Scholar
  3. Manuel Bodirsky. Complexity Classification in Infinite-Domain constraint satisfaction. Mémoire d'habilitation à diriger des recherches, Université Diderot - Paris 7. Available at arXiv:1201.0856, 2012. Google Scholar
  4. Manuel Bodirsky. Ramsey Classes: Examples and Constructions. To appear in the Proceedings of the 25th British Combinatorial Conference; arXiv:1502.05146, 2015. Google Scholar
  5. Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The reducts of the homogeneous binary branching C-relation. Preprint arXiv:1408.2554, 2014. Google Scholar
  6. Manuel Bodirsky and Jan Kára. The Complexity of Equality Constraint Languages. Theory of Computing Systems, 3(2):136-158, 2008. A conference version appeared in the proceedings of Computer Science Russia (CSR'06). Google Scholar
  7. Manuel Bodirsky and Jan Kára. The Complexity of Temporal Constraint Satisfaction Problems. Journal of the ACM, 57(2):1-41, 2009. An extended abstract appeared in the Proc. of the Symp. on Theory of Computing (STOC'08). Google Scholar
  8. Manuel Bodirsky and Jens K. Mueller. Rooted Phylogeny Problems. Logical Methods in Computer Science, 7(4), 2011. An extended abstract appeared in the proc. of ICDT'10. Google Scholar
  9. Manuel Bodirsky and Jaroslav Nešetřil. Constraint Satisfaction with Countable Homogeneous Templates. Journal of Logic and Computation, 16(3):359-373, 2006. Google Scholar
  10. Manuel Bodirsky and Michael Pinsker. Reducts of Ramsey structures. AMS Contemporary Mathematics, vol. 558, pages 489-519, 2011. Google Scholar
  11. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. In STOC, pages 655-664, 2011. Preprint of the long version available at arxiv.org/abs/1011.2894. Google Scholar
  12. Manuel Bodirsky and Michael Pinsker. Topological Birkhoff. Transactions of the American Mathematical Society, 367:2527-2549, 2015. Google Scholar
  13. Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projective clone homomorphisms. Preprint, available at ArXiv:1409.4601, 2014. Google Scholar
  14. Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. Journal of Symbolic Logic, 78(4):1036-1054, 2013. A conference version appeared in the Proceedings of LICS 2011. Google Scholar
  15. V. G. Bodnarčuk, Lev A. Kalužnin, Victor Kotov, and Boris A. Romov. Galois theory for Post algebras, part I and II. Cybernetics, 5:243-539, 1969. Google Scholar
  16. David Bryant. Building Trees, Hunting for Trees, and Comparing Trees. PhD-thesis at the University of Canterbury, 1997. Google Scholar
  17. Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005. Google Scholar
  18. Peter J. Cameron. Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990. Google Scholar
  19. Hubie Chen. A rendezvous of Logic, Complexity, and Algebra. SIGACT News, 37(4):85-114, 2006. Google Scholar
  20. David Geiger. Closed Systems of functions and predicates. Pacific Journal of Mathematics, 27:95-100, 1968. Google Scholar
  21. Wilfrid Hodges. Model theory. Cambridge University Press, Cambridge, 1993. Google Scholar
  22. Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185-204, 1998. Google Scholar
  23. Klaus Leeb. Vorlesungen über Pascaltheorie, volume 6 of Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung. Friedrich-Alexander-Universität Erlangen-Nürnberg, 1973. Google Scholar
  24. Meei Pyng Ng, Mike Steel, and Nicholas C. Wormald. The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees. Discrete Applied Mathematics, 98:227-235, 2000. Google Scholar
  25. Michael Steel. The complexity of Reconstructing Trees from Qualitative Charaters and Subtrees. Journal of Classification, 9:91-116, 1992. Google Scholar
  26. Ágnes Szendrei. Clones in universal algebra. Séminaire de Mathématiques Supérieures. Les Presses de l'Université de Montréal, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact