Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets

Miklós Csurös*, Ming Yang Kao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We give a greedy learning algorithm for reconstructing an evolutionary tree based on a certain harmonic average on triplets of terminal taxa. After the pairwise distances between terminal taxa are estimated from sequence data, the algorithm runs in script O sign(n2) time using script O sign(n) work space, where n is the number of terminal taxa. These time and space complexities are optimal in the sense that the size of an input distance matrix is n2 and the size of an output tree is n. Moreover, in the Jukes-Cantor model of evolution, the algorithm recovers the correct tree topology with high probability using sample sequences of length polynomial in (1) n, (2) the logarithm of the error probability, and (3) the inverses of two small parameters.

Original languageEnglish (US)
Pages (from-to)306-322
Number of pages17
JournalSIAM Journal on Computing
Volume31
Issue number1
DOIs
StatePublished - 2001

Keywords

  • Computational learning
  • Evolutionary trees
  • Harmonic greedy triplets
  • The Jukes-Cantor model of evolution

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets'. Together they form a unique fingerprint.

Cite this