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

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

In Algorithmica, Special issue on ISAAC 2001, volume 38(2), pages 377-395, 2004.

Abstract

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris and Meacham. 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, where all internal nodes have degree three, in time O(nlog n). The previous best algorithm for the problem uses time O(n2).

Copyright notice

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

Online version

algorithmica04.pdf (300 Kb)

DOI

10.1007/s00453-003-1065-y

BIBTEX entry

@article{algorithmica04,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen",
  doi = "10.1007/s00453-003-1065-y",
  issn = "0178-4617",
  journal = "Algorithmica, Special issue on ISAAC 2001",
  number = "2",
  pages = "377-395",
  title = "Computing the Quartet Distance Between Evolutionary Trees in Time $O(n\log n)$",
  volume = "38",
  year = "2004"
}

Other versions