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

Andreas Sand, Gerth Stølting Brodal, Rolf Fagerberg, Christian Nørgaard Storm Pedersen, and Thomas Mailund

In BMC Bioinformatics, volume 14(Suppl 2), S18 pages, 2013.

Abstract

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.

Copyright notice

BioMed Central Open Access

Online version

bmc13.pdf (721 Kb)

DOI

10.1186/1471-2105-14-S2-S18

BIBTEX entry

@article{bmc13,
  author = "Andreas Sand and Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen and Thomas Mailund",
  doi = "10.1186/1471-2105-14-S2-S18",
  issn = "1471-2105",
  journal = "BMC Bioinformatics",
  number = "Suppl 2",
  pages = "S18",
  title = "A practical $O(n \log^2 n)$ time algorithm for computing the triplet distance on binary trees",
  volume = "14",
  year = "2013"
}

Other versions