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).
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2016, 74 (4), pp.1386-1403. 〈10.1007/s00453-015-0005-y〉
Liste complète des métadonnées

Contributeur : Isabelle Gouat <>
Soumis le : mardi 19 juillet 2016 - 14:20:19
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral




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〉



Consultations de la notice