Walks on SPR neighborhoods

Area of Science:

• Phylogenetics
• Computational Biology
• Graph Theory

Background:

• Phylogenetic trees represent evolutionary relationships.
• Nearest-neighbor-interchange (NNI) moves transform one tree to another.
• Subtree-prune-and-regraft (SPR) neighborhoods encompass trees reachable by SPR operations.

Purpose of the Study:

• To determine tight bounds on the shortest nearest-neighbor-interchange (NNI)-walks visiting all trees within a subtree-prune-and-regraft (SPR) neighborhood.
• To address Bryant’s Second Combinatorial Challenge and the Penny Ante Problem.

Main Methods:

• Defining an NNI-walk as a sequence of trees connected by single NNI moves.
• Analyzing the relationship between NNI-walk length and the size of the SPR neighborhood for unrooted binary trees.

Main Results:

• The shortest NNI-walk visiting all trees in an SPR neighborhood of a given unrooted binary tree with n leaves requires Θ(n²) additional steps beyond the number of trees in the neighborhood.
• Established tight bounds for these shortest walks.

Conclusions:

• The study provides a precise quantitative answer to long-standing combinatorial problems in phylogenetics.
• The findings offer insights into the topological space of phylogenetic trees and the efficiency of tree transformations.