Computing the All-Pairs Quartet Distance on a set of Evolutionary Trees

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

In Journal of Bioinformatics and Computational Biology, volume 6(1), pages 37-50, 2008.


We present two algorithms for calculating the quartet distance between all pairs of trees in a set of binary evolutionary trees on a common set of species. The algorithms exploit common substructure among the trees to speed up the pairwise distance calculations, thus performing significantly better on large sets of trees compared to performing distinct pairwise distance calculations, as we illustrate experimentally, where we see a speedup factor of around 130 in the best case.

Copyright notice

Copyright © 2008 World Scientific Publishing Company

Online version

jbcb08.pdf (497 Kb)



BIBTEX entry

  author = "Martin Stissing and Thomas Mailund and Christian N{\o}rgaard Storm Pedersen and Gerth St{\o}lting Brodal and Rolf Fagerberg",
  doi = "10.1142/S0219720008003266",
  issn = "0219-7200",
  journal = "Journal of Bioinformatics and Computational Biology",
  number = "1",
  pages = "37-50",
  title = "Computing the All-Pairs Quartet Distance on a set of Evolutionary Trees",
  volume = "6",
  year = "2008"

Other versions