Two strikes against perfect phylogeny

Hans L. Bodlaender, Mike R. Fellows, Tandy J. Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

One of the major efforts in molecular biology is the computation of phylogenies for species sets. A longstanding open problem in this area is called the Perfect Phylogeny problem. For almost two decades the complexity of this problem remained open, with progress limited to polynomial time algorithms for a few special cases, and many relaxations of the problem shown to be NP-Complete. From an applications point of view, the problem is of interest both in its general form, where the number of characters may vary, and in its fixed-parameter form. The Perfect Phylogeny problem has been shown to be equivalent to the problem of triangulating colored graphs[30]. It has also been shown recently that for a given fixed number of characters the yes-instances have bounded treewidth[45], opening the possibility of applying methodologies for bounded treewidth to the fixed-parameter form of the problem. We show that the Perfect Phylogeny problem is difficult in two different ways. We show that the general problem is NP-Complete, and we show that the various finite-state approaches for bounded treewidth cannot be applied to the fixed-parameter forms of the problem.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 19th International Colloquium, Proceedings
EditorsWerner Kuich
PublisherSpringer-Verlag
Pages273-283
Number of pages11
Volume623
ISBN (Print)9783540557197
DOIs
StatePublished - 1992
Externally publishedYes
Event19th International Colloquium on Automata, Languages, and Programming, ICALP 1992 - Wien, Austria
Duration: Jul 13 1992Jul 17 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume623 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th International Colloquium on Automata, Languages, and Programming, ICALP 1992
CountryAustria
CityWien
Period7/13/927/17/92

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Two strikes against perfect phylogeny'. Together they form a unique fingerprint.

  • Cite this

    Bodlaender, H. L., Fellows, M. R., & Warnow, T. J. (1992). Two strikes against perfect phylogeny. In W. Kuich (Ed.), Automata, Languages and Programming - 19th International Colloquium, Proceedings (Vol. 623, pp. 273-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 623 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-55719-9_80