### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 186-195 |

Number of pages | 10 |

State | Published - 2001 |

Externally published | Yes |

Event | 2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001 |

### Other

Other | 2001 Operating Section Proceedings, American Gas Association |
---|---|

Country | United States |

City | Dallas, TX |

Period | 4/30/01 → 5/1/01 |

### Fingerprint

### Keywords

- Algorithms
- Human factors
- Theory
- Verification

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

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 -