|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
The evolutionary relationship for a set of species can be described by an evolutionary tree, which is a rooted tree where the leaves correspond to the species, and the internal nodes correspond to speciation events, i.e. the points in time where the evolution has diverged in different directions. One method for comparing two evolutionary trees is to define a distance measure between trees, and compare the two trees by computing this distance. Many different distance measures have been defined. Among these is the quartet distance, proposed by Estabrook, McMorris and Meacham in 1985. 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. The straight-forward way to compute the quartet distance takes O(n4) time. Algorithms with running times O(n3) and O(n2) have previously been proposed. We present an algorithm for computing the quartet distance in time O(n log n). The talk will highlight a couple of generic but perhaps not too well-known algorithmic tools and tricks. This is joint work with Gerth Stølting Brodal and Christian N. S. Pedersen.
SDU HOME | IMADA HOME | Previous Page Last modified: May 10, 2004. Joan Boyar (joan@imada.sdu.dk) |