Ranked Subtree Prune and Regraft

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Phylogenetic time trees model evolutionary histories, crucial for understanding virus transmission and cancer evolution.
• Reconstructing time trees often uses Bayesian inference with Markov Chain Monte Carlo (MCMC) sampling.
• Existing tree rearrangement operations like Subtree Prune and Regraft (SPR) are well-studied, but time tree variants are less understood.

Purpose of the Study:

• To introduce and study novel treespaces based on ranked Subtree Prune and Regraft (SPR) operations for phylogenetic time trees.
• To analyze algorithmic properties, computational complexity, and distances within these new treespaces.
• To compare these novel treespaces with existing tree rearrangement spaces.

Main Methods:

• Modification of the classical SPR rearrangement operation applied to ranked phylogenetic trees.
• Analysis of algorithmic properties, focusing on distance computation complexity.
• Comparison with established tree rearrangement based treespaces.

Main Results:

• Introduction of two novel treespaces based on ranked SPR operations.
• Characterization of algorithmic properties, including distance computation complexity.
• Demonstration of the counterintuitive finding that adding leaves can decrease ranked SPR distance.

Conclusions:

• The newly defined ranked SPR treespaces offer a framework for analyzing time tree algorithms.
• The counterintuitive distance property has implications for time tree sampling, particularly with uncertain taxa.
• Further study of these treespaces can enhance comparative analysis of phylogenetic inference methods.