Stochastic safety radius on Neighbor-Joining method and Balanced Minimal Evolution on small trees

2015/07/31 by Jing Xi, Jin Xie, Xi, Jing +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Genetic diversity and population structure #Genomics and Phylogenetic Studies #math.CO #q-bio.PE

paper · pdf · doi:10.48550/arxiv.1507.08734

6 figures. 12 pages

arxiv created 2015/07/31 · arxiv updated 2015/08/03

Abstract

A distance-based method to reconstruct a phylogenetic tree with n leaves takes a distance matrix, n × n symmetric matrix with 0s in the diagonal, as its input and reconstructs a tree with n leaves using tools in combinatorics. A safety radius is a radius from a tree metric (a distance matrix realizing a true tree) within which the input distance matrices must all lie in order to satisfy a precise combinatorial condition under which the distance-based method is guaranteed to return a correct tree. A stochastic safety radius is a safety radius under which the distance-based method is guaranteed to return a correct tree within a certain probability. In this paper we investigated stochastic safety radii for the neighbor-joining (NJ) method and balanced minimal evolution (BME) method for n = 5.

Related

• A 'stochastic safety radius' for distance-based tree reconstruction
• Optimality of the Neighbor Joining Algorithm and Faces of the Balanced Minimum Evolution Polytope
• On the optimality of the neighbor-joining algorithm
• Why neighbor-joining works
• Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance