Computing the Quartet Distance between Evolutionary Trees in Time O( n log n) |
| |
Authors: | Gerth Stølting Brodal Rolf Fagerberg and Christian NS Pedersen |
| |
Affiliation: | (1) Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Århus C, Denmark |
| |
Abstract: | Evolutionary trees describing the relationship for a set of species
are central in evolutionary biology, and quantifying differences
between evolutionary trees is therefore an important task. The
quartet distance is a distance measure between trees previously
proposed by Estabrook, McMorris, and Meacham. The quartet distance
between two unrooted evolutionary trees is the number of quartet
topology differences 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, where all internal
nodes have degree three, in time O(n log n. The previous best
algorithm for the problem uses time O(n
2). |
| |
Keywords: | Evolutionary trees Distance measures Quartet distance Hierarchical decompositions |
本文献已被 SpringerLink 等数据库收录! |
|