Defining Phylogenetic Network Distances Using Cherry Operations.

Area of Science:

• Computational Biology
• Phylogenetics
• Graph Theory

Background:

• Cherry-picking operations in phylogenetic networks have applications in network analysis and comparison.
• These operations can reveal structural similarities and aid in problems like network hybridization.

Purpose of the Study:

• To introduce and analyze novel network distances derived from cherry-picking operations and their reverse.
• To explore the computational complexity and relationships between these new distance measures.

Main Methods:

• Devised four new distances on phylogenetic networks using cherry-picking and reverse operations.
• Analyzed bounds between these distances and proved the equality of three formulations.
• Investigated the computational complexity of calculating these distances.

Main Results:

• Three of the four devised distances are shown to be equivalent.
• Computing these equivalent distances is NP-hard for networks, even when comparing a tree to a network.
• An efficient quadratic-time algorithm is presented for computing these distances between two trees.

Conclusions:

• The study provides new metrics for comparing phylogenetic networks and trees based on structural operations.
• The findings highlight the computational challenges in network comparison while offering efficient solutions for tree comparison.