A `stochastic safety radius' for distance-based tree reconstruction

DOI10.1007/S00453-015-0005-YzbMATH Open1350.92035arXiv1411.4106OpenAlexW1596078534MaRDI QIDQ289927FDOQ289927

Authors: O. Gascuel, Mike Steel 

Publication date: 31 May 2016

Published in: Algorithmica (Search for Journal in Brave)

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 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).

Full work available at URL: https://arxiv.org/abs/1411.4106

Recommendations

• scientific article; zbMATH DE number 1088265
• scientific article; zbMATH DE number 1113974
• Towards optimal distance functions for stochastic substitution models
• scientific article; zbMATH DE number 2079368
• Robustness of phylogenetic inference based on minimum evolution

zbMATH Keywords

treereconstructionrobustness to random error

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Software, source code, etc. for problems pertaining to biology (92-04)

Cites Work

• Comparison of phylogenetic trees
• Title not available (Why is that?)
• Inferring evolutionary trees with strong combinatorial evidence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Why neighbor-joining works
• Structuring causal trees
• The performance of neighbor-joining methods of phylogenetic reconstruction
• Data model and classification by trees; The minimum variance reduction (MVR) method
• Performance analysis of hierarchical clustering algorithms
• A reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance
• Title not available (Why is that?)
• Determining the Evolutionary Tree Using Experiments
• Robustness of phylogenetic inference based on minimum evolution

Cited In (6)

• Spectral neighbor joining for reconstruction of latent tree models
• Phylogenetic placement problem: a hyperbolic embedding approach
• Towards optimal distance functions for stochastic substitution models
• A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem
• Comparing evolutionary distances via adaptive distance functions
• A tutorial on the balanced minimum evolution problem

Uses Software

• BIONJ

This page was built for publication: A `stochastic safety radius' for distance-based tree reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q289927)