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 |
ASJC Scopus subject areas
- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Discrete Mathematics and Combinatorics