A few logs suffice to build (almost) all trees: Part II

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

Research output: Contribution to journalArticle

Abstract

Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O(n5log n) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.

Original languageEnglish (US)
Pages (from-to)77-118
Number of pages42
JournalTheoretical Computer Science
Volume221
Issue number1-2
DOIs
StatePublished - Jun 28 1999
Externally publishedYes

Fingerprint

Joining
Computer science
Computational complexity
Topology
Polynomials
Closure
Evolutionary Tree
Converge
Random Trees
Biology
Convergence Rate
Computer Science
Rate of Convergence
NP-complete problem

Keywords

  • Distance-based methods
  • Dyadic closure method
  • Evolutionary tree reconstruction
  • Phylogeny
  • Quartet methods
  • Short quartet methods
  • Witness-antiwitness method

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this

A few logs suffice to build (almost) all trees : Part II. / Erdos, Péter L.; Steel, Michael A.; Székely, László A.; Warnow, Tandy.

In: Theoretical Computer Science, Vol. 221, No. 1-2, 28.06.1999, p. 77-118.

Research output: Contribution to journalArticle

Erdos, Péter L. ; Steel, Michael A. ; Székely, László A. ; Warnow, Tandy. / A few logs suffice to build (almost) all trees : Part II. In: Theoretical Computer Science. 1999 ; Vol. 221, No. 1-2. pp. 77-118.
@article{c6dfb9e0198b48e489c0ab24029acd7f,
title = "A few logs suffice to build (almost) all trees: Part II",
abstract = "Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O(n5log n) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.",
keywords = "Distance-based methods, Dyadic closure method, Evolutionary tree reconstruction, Phylogeny, Quartet methods, Short quartet methods, Witness-antiwitness method",
author = "Erdos, {P{\'e}ter L.} and Steel, {Michael A.} and Sz{\'e}kely, {L{\'a}szl{\'o} A.} and Tandy Warnow",
year = "1999",
month = "6",
day = "28",
doi = "10.1016/S0304-3975(99)00028-6",
language = "English (US)",
volume = "221",
pages = "77--118",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

TY - JOUR

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

T2 - Part II

AU - Erdos, Péter L.

AU - Steel, Michael A.

AU - Székely, László A.

AU - Warnow, Tandy

PY - 1999/6/28

Y1 - 1999/6/28

N2 - Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O(n5log n) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.

AB - Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O(n5log n) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.

KW - Distance-based methods

KW - Dyadic closure method

KW - Evolutionary tree reconstruction

KW - Phylogeny

KW - Quartet methods

KW - Short quartet methods

KW - Witness-antiwitness method

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

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

U2 - 10.1016/S0304-3975(99)00028-6

DO - 10.1016/S0304-3975(99)00028-6

M3 - Article

AN - SCOPUS:0001860411

VL - 221

SP - 77

EP - 118

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -