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

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.