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

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

**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**

**BIBT**_{E}X 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"
}