The Complexity of Constructing Evolutionary Trees Using Experiments

Gerth Stølting Brodal
Rolf Fagerberg
Christian N. S. Pedersen
Anna Östlin

January 2001

Abstract:

We present a tight upper and lower bound for constructing evolutionary trees using experiments. We present an algorithm which constructs an evolutionary tree of $n$ species using experiments in time $O(n \log_d n)$, where $d$ is the degree of the constructed tree. We show by an explicit adversary argument that any algorithm for constructing an evolutionary tree of $n$ species using experiments must perform $\Omega(n \log_d n)$ experiments, where $d$ is the degree of the constructed tree

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.