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

View at publisher Summarise with VIRAT
Authors: Kaari Landry, Olivier Tremblay-Savard
Cited by: 0
References: 47

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Representing complex evolutionary relationships, such as hybridization and horizontal gene transfer, increasingly requires phylogenetic networks (over phylogenetic trees). Methods of construction of such networks rely on a measure of difference (a distance) between them to identify discrepancies between the newly built networks and a reference. Here, we focus on the cherry distance, a newly developed distance based on the number of cherry operations required to transform one input network into the other. Our work takes an existing algorithm design to calculate cherry distance on level-1 orchards and refines it using a preprocessing filter that maps reticulated elements of the input networks. We also present a heuristic strategy, which operates on only the most promising substructures of the input. CherryRed is a new, publicly available Rust package, which includes both of these improvements. Using CherryRed, we experimentally show how effective our refinement to the exact algorithm is (and when it is most effective), and we show how our heuristic maintains a high degree of accuracy while making large runtime efficiency gains. Characteristics of cherry distance are explored as well, with experiments on a real data set from the Rose family. Particularly, we compare cherry distance with a network adaptation of the ubiquitous Robinson-Foulds (RF) distance on trees, the soft RF distance (softwired distance). We do so with a common rearrangement operation (rooted nearest-neighbor interchange) and a leaf-moving operation, to show a higher degree of sensitivity in cherry distance, and a natural reflection of the number of taxa that are impacted by changes in the network.

Fields of Study & Subjects

Genomics and Phylogenetic Studies Plant Diversity and Evolution Fractal and DNA sequence analysis

Publication details

Journal / source
Journal of Computational Biology
Volume
33
Issue
4
Pages
518–534
Publication date
28 March 2026
Language
EN