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

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

Technical Report, ALCOMFT-TR-01-131, ALCOM-FT, 12 pages, May 2001.

Abstract

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology. Comparing evolutionary trees to quantify differences arising when estimating trees using different methods or data is a fundamental problem. 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). 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.

Online version

alcomft-tr-01-131.pdf (202 Kb)

BIBTEX entry

@techreport{alcomft-tr-01-131,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-01-131",
  pages = "12",
  title = "Computing the Quartet Distance Between Evolutionary Trees in Time {$O(n\log^2 n)$}",
  year = "2001"
}