ALCOMFT-TR-02-54

Gerth Stølting Brodal, Rolf Fagerberg and Christian N. S. Pedersen
Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)
Århus. Work package 4. 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(nlog n). The previous best algorithm for the problem uses time O(nlog² n).

Postscript file: ALCOMFT-TR-02-54.ps.gz (171 kb).