Background
The evolutionary relationship for a set of species is conveniently described by a tree in which the leaves correspond to the species, and the internal nodes correspond to speciation events. The true evolutionary tree for a set of species is rarely known, so inferring it from obtainable information is of great interest. Many different methods have been developed for this, see e.g. [1] for an overview.
Different methods often yield different inferred trees for the same set of species, and even the same method can give rise to different evolutionary trees for the same set of species when applied to different information about the species. To study such differences in a systematic manner, one must be able to quantify differences between evolutionary trees using well-defined and efficient methods.
One approach for comparing evolutionary trees is to define a distance measure between trees and compare two trees by computing this distance. Several distance measures have been proposed, e.g. the symmetric difference metric [2], the nearest-neighbour interchange metric [3], the subtree transfer distance [4], the Robinson and Foulds distance [5], and the quartet distance [6]. Each distance measure has different properties and reflects different aspects of biology.
This paper is concerned with calculating the quartet distance. A quartet is a set of four species, the quartet topology induced by an evolutionary tree is determined by the minimal topological subtree containing the four species. The four possible quartet topologies of four species are shown in Fig. 1. Given two evolutionary trees on the same set of n species, the quartet distance between them is the number of sets of four species for which the quartet topologies differ in the two trees.
Figure 1  The four possible quartet topologies. The four possible quartet topologies of species a, b, c, d. Topologies (a): ab|cd, (b): ac|bd, and (c): ad|bc are butterfly quartets, while topology (d): ab×cd MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeGadiahceaGeaapguaabeqaceaaaeaacqWGHbqyaeaacqWGIbGyaaGaey41aqBbaeqabiqaaaqaaiabdogaJbqaaiabdsgaKbaaaaa@3501@, is a star quartet. Steel and Penny [7] pointed at Doucettes unpublished work [8] which presented an algorithm for computing the quartet distance in time O(n3), where n is the number of species. Bryant et al. in [9] presented an improved algorithm which computes the quartet distance in time O(n2) for binary trees. Brodal et al. in [10] showed how to compute the quartet distance in time O(n log n) considering binary trees. For arbitrary degree trees, the quartet distance can be calculated in time O(n3) or O(n2d2), where d is the maximum degree of any node in any of the two trees, as shown by Christiansen et al. [11].