Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope.

Area of Science:

• Phylogenetics
• Computational Biology
• Evolutionary Biology

Background:

• Balanced Minimum Evolution (BME) is a statistically consistent distance-based method for phylogenetic tree reconstruction from molecular data.
• The BME method is equivalent to optimizing a linear functional over the BME polytope, the convex hull of BME vectors.
• The Neighbor Joining (NJ) Algorithm is a greedy optimization of the BME principle, with prior studies exploring when NJ yields a BME tree.

Purpose of the Study:

• To elucidate the geometric structure of the BME polytope.
• To strengthen the understanding of the relationship between the BME method and the NJ Algorithm.
• To explore the conditions under which the NJ Algorithm produces BME trees.

Main Methods:

• Proving that subtree-prune-regraft moves correspond to edges of the BME polytope.
• Describing a family of faces of the BME polytope parameterized by disjoint clades.
• Demonstrating that these clade-faces are themselves smaller-dimensional BME polytopes.

Main Results:

• Any subtree-prune-regraft move between binary trees corresponds to an edge of the BME polytope.
• A family of clade-faces within the BME polytope are identified as lower-dimensional BME polytopes.
• For any node-joining order, a distance matrix exists where NJ yields the BME tree.
• The BME cone and NJ cones associated with a tree T have an intersection of positive measure.

Conclusions:

• The geometric structure of the BME polytope is significantly elucidated by subtree-prune-regraft moves.
• The connection between BME and NJ algorithms is strengthened, showing NJ can yield BME trees under specific conditions.
• The findings contribute to a deeper theoretical understanding of phylogenetic tree reconstruction methods.