Computing the Quartet Distance Between Evolutionary Trees of Bounded Degree

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

In Proc. 5th Asia Pacific Bioinformatics Conference, volume 5 of Advances in Bioinformatics & Computational Biology, pages 101-110. Imperial College Press, 2007.


We present an algorithm for calculating the quartet distance between two evolutionary trees of bounded degree on a common set of n species. The previous best algorithm has running time O(d2 n2) when considering trees, where no node is of more than degree d. The algorithm developed herein has running time O(d9 n log n)) which makes it the first algorithm for computing the quartet distance between non-binary trees which has a sub-quadratic worst case running time.

Copyright notice

Copyright © 2007 by Imperial College Press

Online version

apbc07qdist.pdf (241 Kb)



BIBTEX entry

  author = "Martin Stissing and Christian N{\o}rgaard Storm Pedersen and Thomas Mailund and Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 5th Asia Pacific Bioinformatics Conference",
  doi = "10.1142/9781860947995_0013",
  isbn = "978-1-86094-783-4",
  pages = "101-110",
  publisher = "Imperial College Press",
  series = "Advances in Bioinformatics \& Computational Biology",
  title = "Computing the Quartet Distance Between Evolutionary Trees of Bounded Degree",
  volume = "5",
  year = "2007"