Disk-covering, a fast-converging method for phylogenetic tree reconstruction

Daniel H. Huson, Scott M. Nettles, Tandy J. Warnow

Research output: Contribution to journalArticle

Abstract

The evolutionary history of a set of species is represented by a phylogenetic tree, which is a rooted, leaf-labeled tree, where internal nodes represent ancestral species and the leaves represent modern day species. Accurate (or even boundedly inaccurate) topology reconstructions of large and divergent trees from realistic length sequences have long been considered one of the major challenges in systematic biology. In this paper, we present a simple method, the Disk-Covering Method (DCM), which boosts the performance of base phylogenetic methods under various Markov models of evolution. We analyze the performance of DCM-boosted distance methods under the Jukes- Cantor Markov model of biomolecular sequence evolution, and prove that for almost all trees, polylogarithmic length sequences suffice for complete accuracy with high probability, while polynomial length sequences always suffice. We also provide an experimental study based upon simulating sequence evolution on model trees. This study confirms substantial reductions in error rates at realistic sequence lengths.

Original languageEnglish (US)
Pages (from-to)369-386
Number of pages18
JournalJournal of Computational Biology
Volume6
Issue number3-4
DOIs
StatePublished - Sep 1 1999
Externally publishedYes

Keywords

  • Algorithms
  • Biomolecular data
  • Chordal graphs
  • Clustering
  • Evolution
  • Jukes Cantor
  • Phylogenetic trees

ASJC Scopus subject areas

  • Molecular Biology
  • Genetics

Fingerprint Dive into the research topics of 'Disk-covering, a fast-converging method for phylogenetic tree reconstruction'. Together they form a unique fingerprint.

  • Cite this