Constructing phylogenetic trees efficiently using compatibility criteria

Tandy J. Warnow

doi:10.1080/0028825X.1993.10419501

Constructing phylogenetic trees efficiently using compatibility criteria

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

Abstract

The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990.

Original language	English (US)
Pages (from-to)	239-248
Number of pages	10
Journal	New Zealand Journal of Botany
Volume	31
Issue number	3
DOIs	https://doi.org/10.1080/0028825X.1993.10419501
State	Published - Jul 1 1993
Externally published	Yes

Keywords

Algorithms
Evolution
Phylogenetic tree

ASJC Scopus subject areas

Ecology, Evolution, Behavior and Systematics
Plant Science

Online availability

10.1080/0028825X.1993.10419501

Library availability

Discover UIUC Full Text

Cite this

@article{2e9ebb3e0cbf45d5bb4de530943844f7,

title = "Constructing phylogenetic trees efficiently using compatibility criteria",

abstract = "The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990.",

keywords = "Algorithms, Evolution, Phylogenetic tree",

author = "Warnow, {Tandy J.}",

note = "Funding Information: The author was supported by NSF Grants CCR88-13632 and DMS9005833, and by the U.S. Department of Energy under Contract DE-AC04-76DP00789. Most of the author's work discussed in this paper was co-authored, and thanks are thus due to Sampath Kannan, Buck McMorris, and Tom Wimer. The referees for the paper (Mike Steel and an anonymous reviewer) are thanked for their thoughtful comments.",

year = "1993",

month = jul,

day = "1",

doi = "10.1080/0028825X.1993.10419501",

language = "English (US)",

volume = "31",

pages = "239--248",

journal = "New Zealand Journal of Botany",

issn = "0028-825X",

publisher = "Taylor and Francis Ltd.",

number = "3",

}

TY - JOUR

T1 - Constructing phylogenetic trees efficiently using compatibility criteria

AU - Warnow, Tandy J.

N1 - Funding Information: The author was supported by NSF Grants CCR88-13632 and DMS9005833, and by the U.S. Department of Energy under Contract DE-AC04-76DP00789. Most of the author's work discussed in this paper was co-authored, and thanks are thus due to Sampath Kannan, Buck McMorris, and Tom Wimer. The referees for the paper (Mike Steel and an anonymous reviewer) are thanked for their thoughtful comments.

PY - 1993/7/1

Y1 - 1993/7/1

N2 - The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990.

AB - The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990.

KW - Algorithms

KW - Evolution

KW - Phylogenetic tree

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

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

U2 - 10.1080/0028825X.1993.10419501

DO - 10.1080/0028825X.1993.10419501

M3 - Article

AN - SCOPUS:25444526825

SN - 0028-825X

VL - 31

SP - 239

EP - 248

JO - New Zealand Journal of Botany

JF - New Zealand Journal of Botany

IS - 3

ER -

Constructing phylogenetic trees efficiently using compatibility criteria

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this