Loading...
Please wait, while we are loading the content...
Similar Documents
Fast Recovery of Evolutionary Trees through Harmonic Greedy Triplets (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Csürös, Miklós Kao, Ming-Yang |
| Description | We give a greedy learning algorithm for reconstructing an evolutionary tree based on a harmonic average on triplets of terminal taxa. After the pairwise distances between terminal taxa are computed, this algorithm runs in quadratic time in the number n of terminal taxa. In the Jukes-Cantor model of evolution generalized for an arbitrary alphabet, the algorithm is mathematically proven to require sample sequences of length only polynomial in n to recover the correct tree topology with high probability. 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. 1 Introduction Algorithms for reconstructing evolutionary trees are principal tools in biology [17, 19, 3, 32]. These algorithms usually compare aligned character sequences for the terminal taxa in question to infer their evolutionary relationships [30]. In the past, such characters were often categorical variable... |
| File Format | |
| Language | English |
| Publisher Date | 1998-01-01 |
| Publisher Institution | in Proceedings of the 10th An164 nual ACM-SIAM Symposium on Discrete Algorithms (SODA '99 |
| Access Restriction | Open |
| Subject Keyword | Short Sequence Large Tree Correct Tree Topology Sample Sequence Theoretical Analysis Evolutionary Relationship Aligned Character Sequence High Probability Categorical Variable Introduction Algorithm Pairwise Distance Harmonic Greedy Triplet Jukes-cantor Model Terminal Taxon Quadratic Time Principal Tool Simulated Experiment Fast Recovery Evolutionary Tree High Success Rate Arbitrary Alphabet Harmonic Average |
| Content Type | Text |
| Resource Type | Article |
