On the complexity of uSPR distance.

Area of Science:

• Computational Biology
• Phylogenetics
• Graph Theory

Background:

• The subtree prune and regraft (uSPR) distance is a key metric for comparing phylogenetic trees.
• Understanding the computational complexity of uSPR distance is crucial for evolutionary analysis.
• Steel's conjecture addresses the stability of uSPR distance under specific tree transformations.

Purpose of the Study:

• To establish the fixed-parameter tractability of computing uSPR distance for unrooted trees.
• To investigate the preservation of uSPR distance under chain reduction operations.
• To improve upon established lower bounds for uSPR distance under chain reduction.

Main Methods:

• Fixed-parameter tractable algorithms were developed for uSPR distance computation.
• Theoretical analysis was employed to study the effect of chain reduction on uSPR distance.
• Lower bound improvements were derived through mathematical proofs.

Main Results:

• The subtree prune and regraft (uSPR) distance on unrooted trees is proven to be fixed parameter tractable with respect to the distance.
• Significant progress is made on Steel's conjecture regarding the preservation of uSPR distance under chain reduction.
• The study improves upon the lower bounds previously established by Hickey et al.

Conclusions:

• The computational complexity of uSPR distance is better understood, with implications for phylogenetic tree reconstruction.
• The findings provide theoretical support for Steel's conjecture, enhancing the analysis of evolutionary relationships.
• Improved lower bounds offer more precise estimations in evolutionary distance calculations.