Of chicken teeth and mouse eyes, or generalized character compatibility

Craig Benham, Sampath Kannan, Tandy Warnow

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

Abstract

We propose a new model of computation for deriving phylogenetic trees based upon a generalization of qualitative characters. The model we propose is based upon recent experimental research in molecular biology. We show that the general case of determining perfect compatibility of generalized ordered characters is an NP-Complete problem, but can be solved in polynomial time for a special case.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
EditorsZvi Galil, Esko Ukkonen
PublisherSpringer-Verlag
Pages17-26
Number of pages10
ISBN (Print)3540600442, 9783540600442
DOIs
StatePublished - Jan 1 1995
Externally publishedYes
Event6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland
Duration: Jul 5 1995Jul 7 1995

Publication series

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

Other

Other6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995
CountryFinland
CityEspoo
Period7/5/957/7/95

Fingerprint

Compatibility
Mouse
Molecular biology
Models of Computation
Molecular Biology
Phylogenetic Tree
Computational complexity
Polynomial time
NP-complete problem
Polynomials
Character
Model
Generalization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Benham, C., Kannan, S., & Warnow, T. (1995). Of chicken teeth and mouse eyes, or generalized character compatibility. In Z. Galil, & E. Ukkonen (Eds.), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings (pp. 17-26). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937). Springer-Verlag. https://doi.org/10.1007/3-540-60044-2_31

Of chicken teeth and mouse eyes, or generalized character compatibility. / Benham, Craig; Kannan, Sampath; Warnow, Tandy.

Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. ed. / Zvi Galil; Esko Ukkonen. Springer-Verlag, 1995. p. 17-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937).

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

Benham, C, Kannan, S & Warnow, T 1995, Of chicken teeth and mouse eyes, or generalized character compatibility. in Z Galil & E Ukkonen (eds), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 937, Springer-Verlag, pp. 17-26, 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995, Espoo, Finland, 7/5/95. https://doi.org/10.1007/3-540-60044-2_31
Benham C, Kannan S, Warnow T. Of chicken teeth and mouse eyes, or generalized character compatibility. In Galil Z, Ukkonen E, editors, Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Springer-Verlag. 1995. p. 17-26. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-60044-2_31
Benham, Craig ; Kannan, Sampath ; Warnow, Tandy. / Of chicken teeth and mouse eyes, or generalized character compatibility. Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. editor / Zvi Galil ; Esko Ukkonen. Springer-Verlag, 1995. pp. 17-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{05bd6ff859b94bb18794ffa574352b68,
title = "Of chicken teeth and mouse eyes, or generalized character compatibility",
abstract = "We propose a new model of computation for deriving phylogenetic trees based upon a generalization of qualitative characters. The model we propose is based upon recent experimental research in molecular biology. We show that the general case of determining perfect compatibility of generalized ordered characters is an NP-Complete problem, but can be solved in polynomial time for a special case.",
author = "Craig Benham and Sampath Kannan and Tandy Warnow",
year = "1995",
month = "1",
day = "1",
doi = "10.1007/3-540-60044-2_31",
language = "English (US)",
isbn = "3540600442",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "17--26",
editor = "Zvi Galil and Esko Ukkonen",
booktitle = "Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings",

}

TY - GEN

T1 - Of chicken teeth and mouse eyes, or generalized character compatibility

AU - Benham, Craig

AU - Kannan, Sampath

AU - Warnow, Tandy

PY - 1995/1/1

Y1 - 1995/1/1

N2 - We propose a new model of computation for deriving phylogenetic trees based upon a generalization of qualitative characters. The model we propose is based upon recent experimental research in molecular biology. We show that the general case of determining perfect compatibility of generalized ordered characters is an NP-Complete problem, but can be solved in polynomial time for a special case.

AB - We propose a new model of computation for deriving phylogenetic trees based upon a generalization of qualitative characters. The model we propose is based upon recent experimental research in molecular biology. We show that the general case of determining perfect compatibility of generalized ordered characters is an NP-Complete problem, but can be solved in polynomial time for a special case.

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

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

U2 - 10.1007/3-540-60044-2_31

DO - 10.1007/3-540-60044-2_31

M3 - Conference contribution

AN - SCOPUS:84957883999

SN - 3540600442

SN - 9783540600442

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

SP - 17

EP - 26

BT - Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings

A2 - Galil, Zvi

A2 - Ukkonen, Esko

PB - Springer-Verlag

ER -