Hen's Teeth and Whale's Feet: Generalized Characters and Their Compatibility

Craig Benham, Sampath Kannan, Michael Paterson, Tandy Warnow

Research output: Contribution to journalArticle

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)
Pages (from-to)515-525
Number of pages11
JournalJournal of Computational Biology
Volume2
Issue number4
DOIs
StatePublished - Jan 1 1995
Externally publishedYes

Fingerprint

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

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

Hen's Teeth and Whale's Feet : Generalized Characters and Their Compatibility. / Benham, Craig; Kannan, Sampath; Paterson, Michael; Warnow, Tandy.

In: Journal of Computational Biology, Vol. 2, No. 4, 01.01.1995, p. 515-525.

Research output: Contribution to journalArticle

Benham, Craig ; Kannan, Sampath ; Paterson, Michael ; Warnow, Tandy. / Hen's Teeth and Whale's Feet : Generalized Characters and Their Compatibility. In: Journal of Computational Biology. 1995 ; Vol. 2, No. 4. pp. 515-525.
@article{6a546fbe19094626befe1432aedddbec,
title = "Hen's Teeth and Whale's Feet: Generalized Characters and Their 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 Michael Paterson and Tandy Warnow",
year = "1995",
month = "1",
day = "1",
doi = "10.1089/cmb.1995.2.515",
language = "English (US)",
volume = "2",
pages = "515--525",
journal = "Journal of Computational Biology",
issn = "1066-5277",
publisher = "Mary Ann Liebert Inc.",
number = "4",

}

TY - JOUR

T1 - Hen's Teeth and Whale's Feet

T2 - Generalized Characters and Their Compatibility

AU - Benham, Craig

AU - Kannan, Sampath

AU - Paterson, Michael

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=0029436724&partnerID=8YFLogxK

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

U2 - 10.1089/cmb.1995.2.515

DO - 10.1089/cmb.1995.2.515

M3 - Article

C2 - 8634903

AN - SCOPUS:0029436724

VL - 2

SP - 515

EP - 525

JO - Journal of Computational Biology

JF - Journal of Computational Biology

SN - 1066-5277

IS - 4

ER -