Constructing big trees from short sequences

Péter L. Erdős, Michael A. Steel, László A. Székely, Tandy J. Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings
EditorsPierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela
PublisherSpringer-Verlag
Pages827-837
Number of pages11
ISBN (Print)3540631658, 9783540631651
StatePublished - Jan 1 1997
Event24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, Italy
Duration: Jul 7 1997Jul 11 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1256
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other24th International Colloquium on Automata, Languages and Programming, ICALP 1997
CountryItaly
CityBologna
Period7/7/977/11/97

Fingerprint

Evolutionary Tree
Topology
Polynomials
Trees (mathematics)
Approximation algorithms
Joining
Statistical Power
Pivot
Polynomial-time Algorithm
Biology
Approximation Algorithms
Polynomial time

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Erdős, P. L., Steel, M. A., Székely, L. A., & Warnow, T. J. (1997). Constructing big trees from short sequences. In P. Degano, R. Gorrieri, & A. Marchetti-Spaccamela (Eds.), Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings (pp. 827-837). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1256). Springer-Verlag.

Constructing big trees from short sequences. / Erdős, Péter L.; Steel, Michael A.; Székely, László A.; Warnow, Tandy J.

Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings. ed. / Pierpaolo Degano; Roberto Gorrieri; Alberto Marchetti-Spaccamela. Springer-Verlag, 1997. p. 827-837 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1256).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Erdős, PL, Steel, MA, Székely, LA & Warnow, TJ 1997, Constructing big trees from short sequences. in P Degano, R Gorrieri & A Marchetti-Spaccamela (eds), Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1256, Springer-Verlag, pp. 827-837, 24th International Colloquium on Automata, Languages and Programming, ICALP 1997, Bologna, Italy, 7/7/97.
Erdős PL, Steel MA, Székely LA, Warnow TJ. Constructing big trees from short sequences. In Degano P, Gorrieri R, Marchetti-Spaccamela A, editors, Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings. Springer-Verlag. 1997. p. 827-837. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Erdős, Péter L. ; Steel, Michael A. ; Székely, László A. ; Warnow, Tandy J. / Constructing big trees from short sequences. Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings. editor / Pierpaolo Degano ; Roberto Gorrieri ; Alberto Marchetti-Spaccamela. Springer-Verlag, 1997. pp. 827-837 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{59e5e1e05c3f4b5aad339fa24654a187,
title = "Constructing big trees from short sequences",
abstract = "The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.",
author = "Erdős, {P{\'e}ter L.} and Steel, {Michael A.} and Sz{\'e}kely, {L{\'a}szl{\'o} A.} and Warnow, {Tandy J.}",
year = "1997",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540631658",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "827--837",
editor = "Pierpaolo Degano and Roberto Gorrieri and Alberto Marchetti-Spaccamela",
booktitle = "Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings",

}

TY - GEN

T1 - Constructing big trees from short sequences

AU - Erdős, Péter L.

AU - Steel, Michael A.

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

AU - Warnow, Tandy J.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

AB - The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

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

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

M3 - Conference contribution

AN - SCOPUS:84951102016

SN - 3540631658

SN - 9783540631651

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 827

EP - 837

BT - Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings

A2 - Degano, Pierpaolo

A2 - Gorrieri, Roberto

A2 - Marchetti-Spaccamela, Alberto

PB - Springer-Verlag

ER -