ALCOMFT-TR-01-131

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

Postscript file: ALCOMFT-TR-01-131.ps.gz (85 kb).