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 Citations (Scopus)

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

Evolutionary Tree
Harmonic
Trees (mathematics)
Topology
Polynomials
Cantor
Greedy Algorithm
Learning algorithms
Learning Algorithm
Theoretical Analysis
Polynomial time
High Accuracy
Polynomial
Estimate
Experiment
Experiments

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.
Csuros, Miklos ; Kao, Ming Yang. / Recovering evolutionary trees through harmonic greedy triplets. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. editor / Anon. SIAM, 1999. pp. 261-270
@inproceedings{fdfefd270e434bbbad0f48d21d354c9b,
title = "Recovering evolutionary trees through harmonic greedy triplets",
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.",
author = "Miklos Csuros and Kao, {Ming Yang}",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
pages = "261--270",
editor = "Anon",
booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "SIAM",

}

Csuros, M & Kao, MY 1999, Recovering evolutionary trees through harmonic greedy triplets. in Anon (ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 261-270, Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 1/17/99.

Recovering evolutionary trees through harmonic greedy triplets. / Csuros, Miklos; Kao, Ming Yang.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Anon. SIAM, 1999. p. 261-270.

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

TY - GEN

T1 - Recovering evolutionary trees through harmonic greedy triplets

AU - Csuros, Miklos

AU - Kao, Ming Yang

PY - 1999/1/1

Y1 - 1999/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0032795125&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032795125&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0032795125

SP - 261

EP - 270

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Anon, null

PB - SIAM

ER -

Csuros M, Kao MY. Recovering evolutionary trees through harmonic greedy triplets. In Anon, editor, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 1999. p. 261-270