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 Berlin Heidelberg
Pages827-837
Number of pages11
ISBN (Print)3540631658, 9783540631651
StatePublished - Jan 1 1997
Externally publishedYes
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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Constructing big trees from short sequences'. Together they form a unique fingerprint.

  • 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 Berlin Heidelberg.