Rearrangement moves on rooted phylogenetic networks

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Phylogenetic tree reconstruction commonly uses local search heuristics and simple rearrangements.
• Existing methods are well-established for trees but lack similar operations for phylogenetic networks.
• Phylogenetic networks model complex evolutionary scenarios including hybridization and horizontal gene transfer.

Purpose of the Study:

• To introduce novel rearrangement operations for phylogenetic networks.
• To ensure comprehensive exploration of the network space, including varying complexity.
• To provide a foundation for improved phylogenetic network reconstruction.

Main Methods:

• Proposed "horizontal" moves to ensure reachability between networks of the same complexity.
• Introduced "vertical" moves for reachability between networks of different complexities.
• Demonstrated that horizontal moves reduce to nearest-neighbor interchange (rNNI) and rooted subtree pruning and regrafting (rSPR) on trees.

Main Results:

• Established reachability results for both horizontal and vertical moves.
• Proved that rNNI moves are local versions of rSPR moves.
• Provided bounds on the sizes of rNNI neighborhoods.
• Showcased the robustness of moves to network complexity and data fit.

Conclusions:

• The new moves provide a systematic way to explore phylogenetic network space.
• These operations are crucial for reconstructing evolutionary histories with reticulate events.
• The work lays the groundwork for more effective phylogenetic network reconstruction algorithms.