Unicyclic networks: compatibility and enumeration

Area of Science:

• Molecular evolutionary biology
• Graph theory
• Phylogenetics

Background:

• Phylogenetic trees are fundamental in evolutionary biology.
• Representing reticulate evolution, like hybridization, requires more complex structures than simple trees.
• Unicyclic networks offer a novel graph-based approach to model these evolutionary scenarios.

Purpose of the Study:

• To introduce and define unicyclic networks as a representation of hybrid evolution.
• To explore the combinatorial properties of unicyclic networks.
• To develop methods for analyzing the compatibility of phylogenetic trees within unicyclic networks.

Main Methods:

• Graph theory: Modifying binary phylogenetic trees by adding edges to form cycles.
• Tree rearrangement operations: Characterizing relationships between trees and unicyclic networks.
• Generating function techniques: Enumerating unicyclic and multicyclic networks.

Main Results:

• Characterization of when a set of binary phylogenetic trees is displayed by a unicyclic network.
• Development of a triple-wise compatibility theorem.
• A fast algorithm for determining 1-cycle compatibility.
• Closed-form expressions for enumerating unicyclic networks.

Conclusions:

• Unicyclic networks provide a valuable framework for studying hybrid evolution in molecular biology.
• The combinatorial properties and developed algorithms offer efficient tools for phylogenetic analysis.
• The enumeration techniques can be extended to more complex network structures.