| 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, and quantifying di#erences between evolutionary trees is an important task. One previously proposed measure for this is the quartet distance. The quartet distance between two unrooted evolutionary trees is the number of quartet topology di#erences between the two trees, where a quartet topology is the topological subtree induced by four species. 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 ). | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||