CherryRed: A Software Implementation of Cherry Distance with a New Optimization and Heuristic.

Area of Science:

• Evolutionary biology
• Bioinformatics
• Computational phylogenetics

Background:

• Phylogenetic trees are insufficient for complex evolutionary histories involving hybridization and horizontal gene transfer.
• Phylogenetic networks are essential for representing these complex evolutionary relationships.
• Measuring differences between phylogenetic networks requires robust distance metrics.

Purpose of the Study:

• To refine algorithms for calculating cherry distance, a metric for phylogenetic network comparison.
• To introduce CherryRed, a Rust package implementing improved cherry distance calculations.
• To evaluate the performance and accuracy of the refined algorithms and a new heuristic strategy.

Main Methods:

• Refinement of an existing algorithm for cherry distance calculation on level-1 orchards.
• Implementation of a preprocessing filter to map reticulated elements in networks.
• Development of a heuristic strategy focusing on promising network substructures.
• Experimental evaluation using simulated and real biological data (Rose family).

Main Results:

• The refined exact algorithm demonstrates effectiveness, particularly under specific conditions.
• The heuristic strategy achieves significant runtime efficiency gains while maintaining high accuracy.
• Cherry distance exhibits higher sensitivity compared to the soft Robinson-Foulds distance.
• Cherry distance naturally reflects the impact of changes on taxa within the network.

Conclusions:

• CherryRed provides efficient and accurate computation of cherry distance for phylogenetic networks.
• The developed methods enhance the analysis of complex evolutionary relationships.
• Cherry distance offers a valuable tool for comparative network analysis in evolutionary biology.