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

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

Research output: Contribution to journalArticle

Abstract

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
Volume14
Issue number2
DOIs
StatePublished - Mar 1999
Externally publishedYes

Fingerprint

Mutation
Polynomials
Evolutionary Tree
Labeled Trees
Phylogenetic Tree
Polynomial-time Algorithm
Biology
Upper and Lower Bounds
Leaves
Model
History
Style
Standards

ASJC Scopus subject areas

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

Cite this

A few logs suffice to build (almost) all trees (I). / Erdos, Péter L.; Steel, Michael A.; Székely, Lászlo A.; Warnow, Tandy.

In: Random Structures and Algorithms, Vol. 14, No. 2, 03.1999, p. 153-184.

Research output: Contribution to journalArticle

Erdos, Péter L. ; Steel, Michael A. ; Székely, Lászlo A. ; Warnow, Tandy. / A few logs suffice to build (almost) all trees (I). In: Random Structures and Algorithms. 1999 ; Vol. 14, No. 2. pp. 153-184.
@article{41608bcb158846959f107daf448792de,
title = "A few logs suffice to build (almost) all trees (I)",
abstract = "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.",
author = "Erdos, {P{\'e}ter L.} and Steel, {Michael A.} and Sz{\'e}kely, {L{\'a}szlo A.} and Tandy Warnow",
year = "1999",
month = "3",
doi = "10.1002/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.3.CO;2-I",
language = "English (US)",
volume = "14",
pages = "153--184",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "2",

}

TY - JOUR

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

AU - Erdos, Péter L.

AU - Steel, Michael A.

AU - Székely, Lászlo A.

AU - Warnow, Tandy

PY - 1999/3

Y1 - 1999/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033480324&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033480324&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.3.CO;2-I

DO - 10.1002/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.3.CO;2-I

M3 - Article

AN - SCOPUS:0033480324

VL - 14

SP - 153

EP - 184

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 2

ER -