Academic Journals Database
Disseminating quality controlled scientific knowledge

Fast calculation of the quartet distance between trees of arbitrary degrees

Author(s): Christiansen Chris | Mailund Thomas | Pedersen Christian | Randers Martin | Stissing Martin

Journal: Algorithms for Molecular Biology
ISSN 1748-7188

Volume: 1;
Issue: 1;
Start page: 16;
Date: 2006;
Original page

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(n3) (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.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions