Counting Cherry Reduction Sequences in Phylogenetic Tree-Child Networks is Counting Linear Extensions

Area of Science:

• Computational Biology
• Phylogenetics
• Network Theory

Background:

• Orchard and tree-child networks, like phylogenetic trees, are reducible via cherry and reticulated cherry deletion.
• The number of reduction sequences provides topological information for these networks.

Purpose of the Study:

• To establish a computational framework for quantifying topological properties of tree-child networks.
• To develop an efficient algorithm for counting network reduction sequences.

Main Methods:

• Demonstrated the equivalence between counting cherry deletion sequences in tree-child networks and counting linear extensions of induced posets.
• Developed a reduction-based algorithm for computing this count.

Main Results:

• The problem of computing the number of reduction sequences is shown to be equivalent to finding linear extensions of the induced poset.
• The proposed algorithm's complexity is bounded by the network's level.

Conclusions:

• This work provides a novel algorithmic approach to analyze tree-child network topology.
• The findings connect network reduction properties to poset theory, offering new avenues for research in phylogenetics and network analysis.