A ‘Stochastic Safety Radius’ for Distance-Based Tree Reconstruction

Olivier Gascuel 1 Mike Steel 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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).
Document type :
Journal articles
Liste complète des métadonnées

Contributor : Isabelle Gouat <>
Submitted on : Tuesday, July 19, 2016 - 2:20:19 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text




Olivier Gascuel, Mike Steel. A ‘Stochastic Safety Radius’ for Distance-Based Tree Reconstruction. Algorithmica, Springer Verlag, 2016, 74 (4), pp.1386-1403. ⟨10.1007/s00453-015-0005-y⟩. ⟨lirmm-01346675⟩



Record views