Computing the Quartet Distance Between Evolutionary Trees in Time O(nlog2 n)

Gerth Stølting Brodal, Rolf Fagerberg, and Christian Nørgaard Storm Pedersen

In Proc. 12th Annual International Symposium on Algorithms and Computation, volume 2223 of Lecture Notes in Computer Science, pages 731-742. Springer Verlag, Berlin, 2001.

Abstract

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is an important task. One previously proposed measure for this is the quartet distance. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper, we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species in time O(nlog2 n). The previous best algorithm runs in time O(n2).

Copyright notice

© Springer-Verlag Berlin Heidelberg 2001. All rights reserved.

Online version

isaac01.pdf (144 Kb)

DOI

10.1007/3-540-45678-3_62

Links

BIBTEX entry

@incollection{isaac01,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen",
  booktitle = "Proc. 12th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/3-540-45678-3_62",
  isbn = "978-3-540-42985-2",
  pages = "731-742",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Computing the Quartet Distance Between Evolutionary Trees in Time {$O(n\log^2 n)$}",
  volume = "2223",
  year = "2001"
}