liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Complexity of Phylogeny Constraint Satisfaction Problems
Technical University of Dresden, Germany.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Vietnam Academy of Science and Technology, Hanoi, Vietnam.
2017 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 18, no 3, 23Article in journal (Refereed) Published
Abstract [en]

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, Leebs Ramsey theorem for rooted trees, and universal algebra.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY , 2017. Vol. 18, no 3, 23
Keyword [en]
Constraint satisfaction problems; computational complexity; phylogenetic reconstruction; Ramsey theory; model theory
National Category
Mathematical Analysis
Identifiers
URN: urn:nbn:se:liu:diva-140982DOI: 10.1145/3105907ISI: 000408665000006OAI: oai:DiVA.org:liu-140982DiVA: diva2:1142297
Note

Funding Agencies|European Research Council (ERC) [257039, 681988]; German Science Foundation (DFG) [622397]; Swedish Research Council (VR) [621-2012-3239]; European Research Council under the European Communitys Seventh Framework Programme [257039]; Austrian Science Fund (FWF) [P27600]; Vietnam National Foundation for Science and Technology Development (NAFOSTED) [101.99-2016.16]

Available from: 2017-09-19 Created: 2017-09-19 Last updated: 2017-09-19

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
ACM Transactions on Computational Logic
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf