Aarhus University Seal

A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review


  • Triplet

    Final published version, 637 KB, PDF document


The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.
Original languageEnglish
JournalB M C Bioinformatics
IssueSuppl 2
Pages (from-to)S18
Number of pages9
Publication statusPublished - 2013
EventThe Asia Pacific Bioinformatics Conference - Vancouver, Canada
Duration: 21 Jan 201324 Jan 2013
Conference number: 11


ConferenceThe Asia Pacific Bioinformatics Conference

Bibliographical note

Also publ. in: Proceedings, 11th Asia Pacific Bioinformatics Conference. Tsinghua University Press, 2013.

See relations at Aarhus University Citationformats


Download statistics

No data available

ID: 52122356