# Computing the Quartet Distance Between Evolutionary Trees in Time *O*(*n*log *n*)

Technical Report, ALCOMFT-TR-02-54, ALCOM-FT, 15 pages, May 2002.

## 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. 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 in time *O*(*n*log *n*).
The previous best algorithm for the problem uses time *O*(*n*log^{2} *n*).

**Online version**
alcomft-tr-02-54.pdf (181 Kb)

**BIBT**_{E}X entry

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