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

Craig Benham; Sampath Kannan; Michael Paterson; Tandy Warnow

doi:10.1089/cmb.1995.2.515

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

Craig Benham, Sampath Kannan, Michael Paterson, Tandy Warnow

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	515-525
Number of pages	11
Journal	Journal of Computational Biology
Volume	2
Issue number	4
DOIs	https://doi.org/10.1089/cmb.1995.2.515
State	Published - 1995
Externally published	Yes

ASJC Scopus subject areas

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

Online availability

10.1089/cmb.1995.2.515

Library availability

Discover UIUC Full Text

Cite this

@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",

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

Y1 - 1995

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

SN - 1066-5277

VL - 2

SP - 515

EP - 525

JO - Journal of Computational Biology

JF - Journal of Computational Biology

IS - 4

ER -

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

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this