Median quartet tree search algorithms using optimal subtree prune and regraft.

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Gene trees often differ from species trees due to biological processes and inference errors.
• Reconciling gene tree discordance with species evolution is a central challenge in phylogenetics.
• Existing methods for species tree inference often rely on heuristics that do not employ hill-climbing strategies.

Purpose of the Study:

• To develop a theoretically grounded, efficient hill-climbing approach for species tree reconstruction.
• To enable the use of subtree prune and regraft (SPR) rearrangements within a hill-climbing search framework.
• To improve upon the optimization scores of existing species tree inference methods.

Main Methods:

• Developed a novel algorithm for optimally placing subtrees within larger trees in quasi-linear time.
• Integrated this subtree placement capability into a hill-climbing search to perform SPR rearrangements.
• Evaluated the method's performance by comparing its optimization score against widely-used phylogenetic inference tools.

Main Results:

• Demonstrated that subtree placement can be performed efficiently, enabling practical hill-climbing searches.
• The proposed hill-climbing approach achieved slightly improved optimization scores compared to methods like ASTRAL.
• While improving the score, the method did not consistently yield more accurate species trees than existing approaches.

Conclusions:

• Theoretical advancements enable efficient hill-climbing for species tree inference using SPR.
• This approach offers a viable alternative to current heuristic methods, particularly for score optimization.
• Future work may focus on enhancing accuracy alongside score optimization in phylogenetic tree reconstruction.