The Complexity of Constructing Evolutionary Trees Using Experiments
Gerth Stølting Brodal, Rolf Fagerberg, Christian
N. S. Pedersen, and Anna Östlin
In Proc. 28th International Colloquium on Automata, Languages,
and Programming, volume 2076 of Lecture Notes in Computer Science,
pages 140-151. Springer Verlag, Berlin, 2001.
Abstract
We present tight upper and lower bounds for the problem of
constructing evolutionary trees in the experiment model. We describe
an algorithm which constructs an evolutionary tree of n species in
time O(nd logd n) using at most n \ceil{d/2}(log2\ceil{d/2}-1 n +
O(1)) experiments for d>2, and at most n(log n + O(1)) experiments for
d=2, where d is the degree of the tree. This improves the previous
best upper bound by a factor Theta(log d). For d=2 the previously best
algorithm with running time O(nlog n) had a bound of 4nlog n on the
number of experiments. By an explicit adversary argument, we show an
Omega(ndlogd n) lower bound, matching our upper bounds and improving
the previous best lower bound by a factor Theta(logd n). Central to
our algorithm is the construction and maintenance of separator trees
of small height, which may be of independent interest.