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.

Abstract

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(d² n²) when considering trees, where no node is of more than degree d. The algorithm developed herein has running time O(d⁹ 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)

DOI

10.1142/9781860947995_0013

BIBT_EX entry

@incollection{apbc07qdist,
  author = "Martin Stissing and Christian Nørgaard Storm Pedersen and Thomas Mailund and Gerth Stø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"
}