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 - 2001
Externally publishedYes
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Other

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

Fingerprint

Absolute convergence
Polynomials
Phylogenetic Tree
Unknown Parameters
Demonstrate
Converge
Polynomial
Requirements

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)

Absolute convergence : True trees from short sequences. / Warnow, Tandy; Moret, Bernard M.E.; John, Katherine St.

Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 186-195.

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

Warnow, T, Moret, BME & John, KS 2001, Absolute convergence: True trees from short sequences. in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 186-195, 2001 Operating Section Proceedings, American Gas Association, Dallas, TX, United States, 4/30/01.
Warnow T, Moret BME, John KS. Absolute convergence: True trees from short sequences. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 186-195
Warnow, Tandy ; Moret, Bernard M.E. ; John, Katherine St. / Absolute convergence : True trees from short sequences. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. pp. 186-195
@inproceedings{6544282997fb4af39a8626b9b6741307,
title = "Absolute convergence: True trees from short sequences",
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.",
keywords = "Algorithms, Human factors, Theory, Verification",
author = "Tandy Warnow and Moret, {Bernard M.E.} and John, {Katherine St}",
year = "2001",
language = "English (US)",
isbn = "0898714907",
pages = "186--195",
booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

}

TY - GEN

T1 - Absolute convergence

T2 - True trees from short sequences

AU - Warnow, Tandy

AU - Moret, Bernard M.E.

AU - John, Katherine St

PY - 2001

Y1 - 2001

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

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

KW - Algorithms

KW - Human factors

KW - Theory

KW - Verification

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

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

M3 - Conference contribution

AN - SCOPUS:64049101566

SN - 0898714907

SP - 186

EP - 195

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

ER -