Absolute convergence: True trees from short sequences

Tandy Warnow, Bernard M.E. Moret, Katherine St John

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

Abstract

Fast-converging methods for reconstructing phylogenetic trees require that the sequences characterizing the taxa be of only polynomial length, a major asset in practice, since real-life sequences are of bounded length. However, of the half-dozen such methods proposed over the last few years, only two fulfill this condition without requiring knowledge of typically unknown parameters, such as the evolutionary rate(s) used in the model; this additional requirement severely limits the applicability of the methods. We say that methods that need such knowledge demonstrate relative fast convergence, since they rely upon an oracle. We focus on the class of methods that do not require such knowledge and thus demonstrate absolute fast convergence. We give a very general construction scheme that not only turns any relative fast-converging method into an absolute fast-converging one, but also turns any statistically consistent method that converges from sequence of length &Ogr;(e &Ogr;(diam(T))) into an absolute fast-converging method.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages186-195
Number of pages10
StatePublished - Dec 1 2001
Externally publishedYes
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

    Fingerprint

Keywords

  • Algorithms
  • Human factors
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Warnow, T., Moret, B. M. E., & John, K. S. (2001). Absolute convergence: True trees from short sequences. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 186-195). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).