Algorithms Mol Biol. 2006 Sep 25;1:16. doi: 10.1186/1748-7188-1-16.
Fast calculation of the quartet distance between trees of arbitrary degrees.
Algorithms for molecular biology : AMB
Chris Christiansen, Thomas Mailund, Christian N S Pedersen, Martin Randers, Martin Stig Stissing
PMID: 16999860
PMCID: PMC1592098 DOI: 10.1186/1748-7188-1-16
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.
References
- Bioinformatics. 2005 Apr 15;21(8):1711-2 - PubMed
- J Theor Biol. 1978 Aug 21;73(4):789-800 - PubMed
Publication Types
