Research

Fast calculation of the quartet distance between trees of arbitrary degrees

Chris Christiansen¹ , Thomas Mailund² , Christian NS Pedersen^1,3 , Martin Randers¹ and Martin Stig Stissing¹

¹  Department of Computer Science, University of Aarhus, Aabogade 34, DK-8200 Århus N, Denmark

²  Department of Statistics, University of Oxford, 1 South Parks Road Oxford OX1 3TG, UK

³  Bioinformatics Research Center, University of Aarhus, Høegh-Guldbergsgade 10, Bldg. 090, DK-8000 Århus C, Denmark

author email corresponding author email

Algorithms for Molecular Biology 2006, 1:16doi:10.1186/1748-7188-1-16

Published:	25 September 2006

Abstract

Background

A number of algorithms have been developed for calculating the quartet distance between two evolutionary trees on the same set of species. The quartet distance is the number of quartets – sub-trees induced by four leaves – that differs between the trees. Mostly, these algorithms are restricted to work on binary trees, but recently we have developed algorithms that work on trees of arbitrary degree.

Results

We present a fast algorithm for computing the quartet distance between trees of arbitrary degree. Given input trees T and T', the algorithm runs in time O(n + |V|·|V'| min{id, id'}) and space O(n + |V|·|V'|), where n is the number of leaves in the two trees, V and V are the non-leaf nodes in T and T', respectively, and id and id' are the maximal number of non-leaf nodes adjacent to a non-leaf node in T and T', respectively. The fastest algorithms previously published for arbitrary degree trees run in O(n³) (independent of the degree of the tree) and O(|V|·|V'|·id·id'), respectively. We experimentally compare the algorithm with existing algorithms for computing the quartet distance for general trees.

Conclusion

We present a new algorithm for computing the quartet distance between two trees of arbitrary degree. The new algorithm improves the asymptotic running time for computing the quartet distance, compared to previous methods, and experimental results indicate that the new method also performs significantly better in practice.