Name
Abstract | ||
|---|---|---|
A variety of algorithms have been proposed for reconstructing trees that show the evolutionary relationships between species by comparing differences in genetic data across present-day species. If the leaf-to-leaf distances in a tree can be accurately estimated, then it is possible to reconstruct this tree from these estimated distances, using polynomial-time methods such as the popular `Neighbor-Joining' algorithm. There is a precise combinatorial condition under which distance-based methods are guaranteed to return a correct tree (in full or in part) based on the requirement that the input distances all lie within some `safety radius' of the true distances. Here, we explore a stochastic analogue of this condition, and mathematically establish upper and lower bounds on this `stochastic safety radius' for distance-based tree reconstruction methods. Using simulations, we show how this notion provides a new way to compare the performance of distance-based tree reconstruction methods. This may help explain why Neighbor-Joining performs so well, as its stochastic safety radius appears close to optimal (while its more classical safety radius is the same as many other less accurate methods). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s00453-015-0005-y | Algorithmica |
Keywords | Field | DocType |
Tree,Reconstruction,Robustness to random error | Discrete mathematics,Combinatorics,Upper and lower bounds,Vantage-point tree,Mathematics,Interval tree | Journal |
Volume | Issue | ISSN |
74 | 4 | 0178-4617 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olivier Gascuel | 1 | 433 | 76.01 |
| Mike Steel | 2 | 270 | 41.87 |