Recovering evolutionary trees through harmonic greedy triplets

Miklos Csuros*, Ming Yang Kao

*Corresponding author for this work

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

13 Scopus citations

Abstract

We give a greedy learning algorithm for reconstructing an evolutionary tree based on a harmonic average on triplets of taxa. This algorithm runs in polynomial time in the input size. Using the Jukes-Cantor model of evolution, our algorithm is mathematically proven to require sample sequences of only polynomial lengths in the number of taxa in order to recover the correct tree topology with high probability. In addition to recovering the topology, the algorithm also estimates the tree edge lengths with high accuracy. Our theoretical analysis is supported by simulated experiments, in which the algorithm has demonstrated high success rates in reconstructing a large tree from short sequences.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors Anon
PublisherSIAM
Pages261-270
Number of pages10
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

    Fingerprint

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Cite this

Csuros, M., & Kao, M. Y. (1999). Recovering evolutionary trees through harmonic greedy triplets. In Anon (Ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 261-270). SIAM.