Tree compatibility and inferring evolutionary history

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

Abstract

The Tree Compatibility Problem is a problem concerned with evolutionary history construction. For a species set S, an S-labelled tree is a tree T along with a labelling L : S→V(T). The Tree Compatibility Problem asks whether a set T of S-labelled trees, each of which describes the evolution of S, is compatible in the sense that there is a single tree T* from which each tree TqqT can be derived by a sequence of edge contractions. Polynomial time algorithms for the Tree Compatibility problem have been known to exist for a long time, with the best being the recent O(n2k) algorithm by Gusfield to determine compatibility of k trees on n species. Recently Gusfield found an O(nk) algorithm for a restricted case of the Tree Compatibility Problem. In this paper, we will present an O(nk) algorithm for the Tree Compatibility Problem, thus achieving linear time. The Perfect Phylogeny Problem is another problem in evolutionary history construction, which has been recently shown to be in P for special cases but NP-Complete for the general case. We will show that we can characterize each instance to the Perfect Phylogeny Problem as an instance to the Tree Compatibility Problem, and thus derive an algorithm for the Perfect Phylogeny Problem. Our algorithm is superior to the other algorithms for Perfect Phylogeny Problem for many realistic cases, such as when the species are defined by molecular data such as amino-acid sequences.

Original languageEnglish (US)
Title of host publicationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages382-391
Number of pages10
StatePublished - Jan 1 1993
Externally publishedYes
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

Fingerprint

Trees (mathematics)
Labeling
Amino acids
Polynomials
Phylogeny

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Warnow, T. (1993). Tree compatibility and inferring evolutionary history. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 382-391). Publ by ACM.

Tree compatibility and inferring evolutionary history. / Warnow, Tandy.

Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, 1993. p. 382-391.

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

Warnow, T 1993, Tree compatibility and inferring evolutionary history. in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, pp. 382-391, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 1/25/93.
Warnow T. Tree compatibility and inferring evolutionary history. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM. 1993. p. 382-391
Warnow, Tandy. / Tree compatibility and inferring evolutionary history. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, 1993. pp. 382-391
@inproceedings{17e7d0d2a507473a8515f2a6e3f7c672,
title = "Tree compatibility and inferring evolutionary history",
abstract = "The Tree Compatibility Problem is a problem concerned with evolutionary history construction. For a species set S, an S-labelled tree is a tree T along with a labelling L : S→V(T). The Tree Compatibility Problem asks whether a set T of S-labelled trees, each of which describes the evolution of S, is compatible in the sense that there is a single tree T* from which each tree TqqT can be derived by a sequence of edge contractions. Polynomial time algorithms for the Tree Compatibility problem have been known to exist for a long time, with the best being the recent O(n2k) algorithm by Gusfield to determine compatibility of k trees on n species. Recently Gusfield found an O(nk) algorithm for a restricted case of the Tree Compatibility Problem. In this paper, we will present an O(nk) algorithm for the Tree Compatibility Problem, thus achieving linear time. The Perfect Phylogeny Problem is another problem in evolutionary history construction, which has been recently shown to be in P for special cases but NP-Complete for the general case. We will show that we can characterize each instance to the Perfect Phylogeny Problem as an instance to the Tree Compatibility Problem, and thus derive an algorithm for the Perfect Phylogeny Problem. Our algorithm is superior to the other algorithms for Perfect Phylogeny Problem for many realistic cases, such as when the species are defined by molecular data such as amino-acid sequences.",
author = "Tandy Warnow",
year = "1993",
month = "1",
day = "1",
language = "English (US)",
pages = "382--391",
booktitle = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Publ by ACM",

}

TY - GEN

T1 - Tree compatibility and inferring evolutionary history

AU - Warnow, Tandy

PY - 1993/1/1

Y1 - 1993/1/1

N2 - The Tree Compatibility Problem is a problem concerned with evolutionary history construction. For a species set S, an S-labelled tree is a tree T along with a labelling L : S→V(T). The Tree Compatibility Problem asks whether a set T of S-labelled trees, each of which describes the evolution of S, is compatible in the sense that there is a single tree T* from which each tree TqqT can be derived by a sequence of edge contractions. Polynomial time algorithms for the Tree Compatibility problem have been known to exist for a long time, with the best being the recent O(n2k) algorithm by Gusfield to determine compatibility of k trees on n species. Recently Gusfield found an O(nk) algorithm for a restricted case of the Tree Compatibility Problem. In this paper, we will present an O(nk) algorithm for the Tree Compatibility Problem, thus achieving linear time. The Perfect Phylogeny Problem is another problem in evolutionary history construction, which has been recently shown to be in P for special cases but NP-Complete for the general case. We will show that we can characterize each instance to the Perfect Phylogeny Problem as an instance to the Tree Compatibility Problem, and thus derive an algorithm for the Perfect Phylogeny Problem. Our algorithm is superior to the other algorithms for Perfect Phylogeny Problem for many realistic cases, such as when the species are defined by molecular data such as amino-acid sequences.

AB - The Tree Compatibility Problem is a problem concerned with evolutionary history construction. For a species set S, an S-labelled tree is a tree T along with a labelling L : S→V(T). The Tree Compatibility Problem asks whether a set T of S-labelled trees, each of which describes the evolution of S, is compatible in the sense that there is a single tree T* from which each tree TqqT can be derived by a sequence of edge contractions. Polynomial time algorithms for the Tree Compatibility problem have been known to exist for a long time, with the best being the recent O(n2k) algorithm by Gusfield to determine compatibility of k trees on n species. Recently Gusfield found an O(nk) algorithm for a restricted case of the Tree Compatibility Problem. In this paper, we will present an O(nk) algorithm for the Tree Compatibility Problem, thus achieving linear time. The Perfect Phylogeny Problem is another problem in evolutionary history construction, which has been recently shown to be in P for special cases but NP-Complete for the general case. We will show that we can characterize each instance to the Perfect Phylogeny Problem as an instance to the Tree Compatibility Problem, and thus derive an algorithm for the Perfect Phylogeny Problem. Our algorithm is superior to the other algorithms for Perfect Phylogeny Problem for many realistic cases, such as when the species are defined by molecular data such as amino-acid sequences.

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

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

M3 - Conference contribution

AN - SCOPUS:0027222351

SP - 382

EP - 391

BT - Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

ER -