Exploring spaces of semi-directed level-1 networks

Area of Science:

• Phylogenetics
• Computational Biology
• Network Theory

Background:

• Semi-directed phylogenetic networks integrate directed and undirected edges, bridging rooted and unrooted network types.
• Existing research extensively analyzes rooted and unrooted phylogenetic networks but lacks exploration of semi-directed network spaces.
• Understanding the structure of semi-directed phylogenetic networks is crucial for developing new reconstruction algorithms.

Purpose of the Study:

• To introduce and analyze a novel rearrangement move, the cut edge transfer (CET), for semi-directed phylogenetic networks.
• To establish the connectedness of the space of semi-directed level-1 networks with a fixed number of reticulations under the CET move.
• To extend this connectedness result to the broader space of all semi-directed level-1 networks on a fixed leaf set.

Main Methods:

• Proposed the cut edge transfer (CET) rearrangement move for semi-directed phylogenetic networks.
• Demonstrated the connectedness of the space of semi-directed level-1 networks with k reticulations using CET.
• Introduced additional moves (R[Formula: see text] and R[Formula: see text]) to establish connectedness for the general space of semi-directed level-1 networks.
• Translated results to show connectedness for rooted level-1 networks under CET.

Main Results:

• The cut edge transfer (CET) move connects the space of semi-directed level-1 networks with a fixed number of reticulations and leaf set.
• Any semi-directed level-1 network with a specific reticulation count and leaf set is reachable from any other via CET sequences.
• The space of all semi-directed level-1 networks on a fixed leaf set is connected through CET and additional reticulation-altering moves.
• The space of rooted level-1 networks with a fixed number of reticulations and leaf set is also shown to be connected under CET.

Conclusions:

• The CET move provides a fundamental tool for navigating and understanding the space of semi-directed phylogenetic networks.
• These findings are significant for algorithms reconstructing semi-directed phylogenetic networks, particularly within the commonly used level-1 space.
• The established connectedness facilitates broader exploration and analysis of evolutionary relationships represented by semi-directed networks.