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

Research output: Contribution to journalArticlepeer-review

17 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(n1.5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

Original languageEnglish (US)
Pages (from-to)54-65
Number of pages12
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1997

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'General techniques for comparing unrooted evolutionary trees'. Together they form a unique fingerprint.

Cite this