A few logs suffice to build (almost) all trees (I)

Péter L. Erdos, Michael A. Steel, Lászlo A. Székely, Tandy J. Warnow

Research output: Contribution to journalArticlepeer-review


A phylogenetic tree, also called an "evolutionary tree," is a leaf-labeled tree which represents the evolutionary history for a set of species, and the construction of such trees is a fundamental problem in biology. Here we address the issue of how many sequence sites are required in order to recover the tree with high probability when the sites evolve under standard Markov-style i.i.d. mutation models. We provide analytic upper and lower bounds for the required sequence length, by developing a new polynomial time algorithm. In particular, we show when the mutation probabilities are bounded the required sequence length can grow surprisingly slowly (a power of log n) in the number n of sequences, for almost all trees.

Original languageEnglish (US)
Pages (from-to)153-184
Number of pages32
JournalRandom Structures and Algorithms
Issue number2
StatePublished - Mar 1999
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'A few logs suffice to build (almost) all trees (I)'. Together they form a unique fingerprint.

Cite this