The Complexity of Constructing Evolutionary Trees Using Experiments

TY - GEN

T1 - The Complexity of Constructing Evolutionary Trees Using Experiments

AU - Brodal, Gerth Stølting

AU - Fagerberg, Rolf

AU - Pedersen, Christian Nørgaard Storm

AU - Östlin, Anna

A2 - Orejas, Farnando

A2 - Spirakis, Poul G.

A2 - Leeuwen, Jan van

N1 - Conference code: 28

PY - 2001

Y1 - 2001

N2 - 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⌈d/2⌉(log2⌈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 θ(log d). For d = 2 the previously best algorithm with running time O(n log n) had a bound of 4n log n on the number of experiments. By an explicit adversary argument, we show an Ω(nd logd n) lower bound, matching our upper bounds and improving the previous best lower bound by a factor θ(logd n). Central to our algorithm is the construction and maintenance of separator trees of small height, which may be of independent interest.

AB - 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⌈d/2⌉(log2⌈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 θ(log d). For d = 2 the previously best algorithm with running time O(n log n) had a bound of 4n log n on the number of experiments. By an explicit adversary argument, we show an Ω(nd logd n) lower bound, matching our upper bounds and improving the previous best lower bound by a factor θ(logd n). Central to our algorithm is the construction and maintenance of separator trees of small height, which may be of independent interest.

KW - Phylogenetic tree

KW - Tree(graph)

KW - Distance

KW - Upper bound

KW - Lower bound

M3 - Article in proceedings

SN - 3-540-42287-0

VL - 2076/2001

SP - 140

EP - 151

BT - Lecture Notes In Computer Science; Vol. 2076

PB - Springer

T2 - 28th International Colloquium on Automata, Languages and Programming

Y2 - 12 July 2001 through 18 July 2001

ER -