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

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

Research output: Contribution to journalArticlepeer-review


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
Issue number3-4
StatePublished - Sep 1999
Externally publishedYes


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

ASJC Scopus subject areas

  • Molecular Biology
  • Genetics


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

Cite this