| Computing the Quartet Distance Between Evolutionary Trees in Time (2001) | |||||||||||||||||
|
|||||||||||||||||
Abstract | |||||||||||||||||
| Evolutionary trees describing the relationship for a set of species are central in evolutionary biology. Comparing evolutionary trees to quantify dierences arising when estimating trees using dierent 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(n log 2 n). The previous best algorithm runs in time O(n 2 ). The quartet distance between two unrooted evolutionary trees is the number of quartet topology dierences between the two trees, where a quartet topology is the topological subtree induced by four species. 1 | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||