2014/11/15 by Olivier Gascuel, Gascuel, Olivier, Mike Steel +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Environmental Science · #FOS: Biological sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #Species Distribution and Climate Change #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1411.4106
18 pages, 1 figure, 4 tables
arxiv created 2014/11/15 · openalex publication_date 2014/11/15 · arxiv updated 2014/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 taxa. 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).