The Complexity of Constructing Evolutionary Trees Using Experiments

Gerth Stølting Brodal, Rolf Fagerberg, Christian Nørgaard Storm Pedersen, Anna Östlin, Farnando Orejas (Editor), Poul G. Spirakis (Editor), Jan van Leeuwen (Editor)

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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 nd/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.
Original languageEnglish
Title of host publicationLecture Notes In Computer Science; Vol. 2076 : Proceedings of the 28th International Colloquium on Automata, Languages and Programming
Number of pages12
Volume2076/2001
PublisherSpringer
Publication date2001
Edition2076 of Lecture Notes in Computer Science
Pages140-151
ISBN (Print)3-540-42287-0
ISBN (Electronic)10.1007/3-540-48224-5
Publication statusPublished - 2001
Event28th International Colloquium on Automata, Languages and Programming - Crete, Greece
Duration: 12 Jul 200118 Jul 2001
Conference number: 28

Conference

Conference28th International Colloquium on Automata, Languages and Programming
Number28
Country/TerritoryGreece
CityCrete
Period12/07/200118/07/2001

Keywords

  • Phylogenetic tree
  • Tree(graph)
  • Distance
  • Upper bound
  • Lower bound

Fingerprint

Dive into the research topics of 'The Complexity of Constructing Evolutionary Trees Using Experiments'. Together they form a unique fingerprint.

Cite this