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
ISBN (Print)9783540557197
DOIs
StatePublished - Jan 1 1992
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

Fingerprint

Phylogeny
Bounded Treewidth
Molecular biology
Computational complexity
Open Problems
Polynomials
NP-complete problem
Colored Graph
Molecular Biology
Polynomial-time Algorithm
Vary
Form
Methodology

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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 (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

Two strikes against perfect phylogeny. / Bodlaender, Hans L.; Fellows, Mike R.; Warnow, Tandy J.

Automata, Languages and Programming - 19th International Colloquium, Proceedings. ed. / Werner Kuich. Springer-Verlag, 1992. p. 273-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 623 LNCS).

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

Bodlaender, HL, Fellows, MR & Warnow, TJ 1992, Two strikes against perfect phylogeny. in W Kuich (ed.), Automata, Languages and Programming - 19th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 623 LNCS, Springer-Verlag, pp. 273-283, 19th International Colloquium on Automata, Languages, and Programming, ICALP 1992, Wien, Austria, 7/13/92. https://doi.org/10.1007/3-540-55719-9_80
Bodlaender HL, Fellows MR, Warnow TJ. Two strikes against perfect phylogeny. In Kuich W, editor, Automata, Languages and Programming - 19th International Colloquium, Proceedings. Springer-Verlag. 1992. p. 273-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-55719-9_80
Bodlaender, Hans L. ; Fellows, Mike R. ; Warnow, Tandy J. / Two strikes against perfect phylogeny. Automata, Languages and Programming - 19th International Colloquium, Proceedings. editor / Werner Kuich. Springer-Verlag, 1992. pp. 273-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cb8bea2461f6496a8433bd3351615f5c,
title = "Two strikes against perfect phylogeny",
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.",
author = "Bodlaender, {Hans L.} and Fellows, {Mike R.} and Warnow, {Tandy J.}",
year = "1992",
month = "1",
day = "1",
doi = "10.1007/3-540-55719-9_80",
language = "English (US)",
isbn = "9783540557197",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "273--283",
editor = "Werner Kuich",
booktitle = "Automata, Languages and Programming - 19th International Colloquium, Proceedings",

}

TY - GEN

T1 - Two strikes against perfect phylogeny

AU - Bodlaender, Hans L.

AU - Fellows, Mike R.

AU - Warnow, Tandy J.

PY - 1992/1/1

Y1 - 1992/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85010120898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010120898&partnerID=8YFLogxK

U2 - 10.1007/3-540-55719-9_80

DO - 10.1007/3-540-55719-9_80

M3 - Conference contribution

AN - SCOPUS:85010120898

SN - 9783540557197

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 273

EP - 283

BT - Automata, Languages and Programming - 19th International Colloquium, Proceedings

A2 - Kuich, Werner

PB - Springer-Verlag

ER -