General techniques for comparing unrooted evolutionary trees

Ming Yang Kao; Tak Wah Lam; Teresa M. Przytycka; Wing Kin Sung; Hing Fung Ting

doi:10.1145/258533.258550

General techniques for comparing unrooted evolutionary trees

Ming Yang Kao^*, Tak Wah Lam, Teresa M. Przytycka, Wing Kin Sung, Hing Fung Ting

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Conference article › peer-review

19 Scopus citations

Abstract

This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n^1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

Original language	English (US)
Pages (from-to)	54-65
Number of pages	12
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/258533.258550
State	Published - 1997
Event	Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA Duration: May 4 1997 → May 6 1997

ASJC Scopus subject areas

Software

Access to Document

10.1145/258533.258550

Cite this

@article{f94f1c5e82fe499598844585baead9b5,

title = "General techniques for comparing unrooted evolutionary trees",

abstract = "This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.",

author = "Kao, \{Ming Yang\} and Lam, \{Tak Wah\} and Przytycka, \{Teresa M.\} and Sung, \{Wing Kin\} and Ting, \{Hing Fung\}",

year = "1997",

doi = "10.1145/258533.258550",

language = "English (US)",

pages = "54--65",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing ; Conference date: 04-05-1997 Through 06-05-1997",

}

TY - JOUR

T1 - General techniques for comparing unrooted evolutionary trees

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Przytycka, Teresa M.

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 1997

Y1 - 1997

N2 - This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

AB - This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

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

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

U2 - 10.1145/258533.258550

DO - 10.1145/258533.258550

M3 - Conference article

AN - SCOPUS:0030642910

SN - 0734-9025

SP - 54

EP - 65

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing

Y2 - 4 May 1997 through 6 May 1997

ER -

General techniques for comparing unrooted evolutionary trees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this