### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Editors | Anon |

Publisher | SIAM |

Pages | 261-270 |

Number of pages | 10 |

State | Published - Jan 1 1999 |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |

### Other

Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 1/17/99 → 1/19/99 |

### Fingerprint

### ASJC Scopus subject areas

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

### Cite this

*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 261-270). SIAM.

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -