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.
AllenBL, SteelM. Subtree transfer operations and their induced metrics on evolutionary trees. Ann Comb, 2001; 5(1):1–15.
2.
AllmanES, BañosH, RhodesJA. NANUQ: A method for inferring species networks from gene trees under the coalescent model. Algorithms Mol Biol, 2019; 14(1):1–25.
3.
AnisimovaM, LiberlesDA, PhilippeH, et al.State-of-the-art methodologies dictate new standards for phylogenetic analysis. BMC Evol Biol, 2013; 13:161.
4.
ArnoldML. Natural hybridization and evolution. Oxford University Press: New York, NY; 1997.
5.
BaptesteE, van IerselL, JankeA, et al.Networks: Expanding evolutionary thinking. Trends Genet, 2013; 29(8):439–441.
6.
BaroniM, SempleC, SteelM. A framework for representing reticulate evolution. Ann Comb, 2005; 8(4):391–408.
7.
BeikoRG. Gene sharing and genome evolution: Networks in trees and trees in networks. Biol Philos, 2010; 25(4):659–673.
8.
BordewichM, LinzS, SempleC. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. J Theor Biol, 2017; 423:1–12.
9.
BordewichM, SempleC. Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. IEEE/ACM Trans Comput Biol Bioinform, 2007; 4(3):458–466.
10.
CardonaG, LlabrésM, RossellóF, et al.Metrics for phylogenetic networks I: Generalizations of the Robinson-Foulds metric. IEEE/ACM Trans Comput Biol Bioinform, 2008a;6(1):46–61.
11.
CardonaG, RossellóF, ValienteG. Extended newick: It is time for a standard representation of phylogenetic networks. BMC Bioinformatics, 2008b;9:532–538.
12.
CardonaG, RossellóF, ValienteG. Tripartitions do not always discriminate phylogenetic networks. Math Biosci, 2008c;211(2):356–370.
13.
DawlingTE, SecorCL. The role of hybridization and introgression in the diversification of animals. Annu Rev Ecol Syst, 1997; 28(1):593–619.
14.
DayWH. Optimal algorithms for comparing trees with labeled leaves. J Classif, 1985; 2(1):7–28.
15.
ErdősPL, SempleC, SteelM. A class of phylogenetic networks reconstructable from ancestral profiles. Math Biosci, 2019; 313:33–40.
16.
FrancisA, HuberKT, MoultonV, et al.Bounds for phylogenetic network space metrics. J Math Biol, 2018; 76(5):1229–1248.
17.
GaboraL, LejinenS, VelozT, et al.A non-phylogenetic conceptual network architecture for organizing classes of material artifacts into cultural lineages. Proceedings of the Annual Meeting of the Cognitive Science Society, Vol. 33; 2011.
18.
GambetteP, Van IerselL, JonesM, et al.Rearrangement moves on rooted phylogenetic networks. PLoS Comput Biol, 2017; 13(8):e1005611.
19.
GouletBE, RodaF, HopkinsR. Hybridization in plants: Old ideas, new techniques. Plant Physiol, 2017; 173(1):65–78.
20.
HarrisonRG, LarsonEL. Hybridization, introgression, and the nature of species boundaries. J Hered, 2014; 105(Suppl 1):795–809.
21.
HuberKT, LinzS, MoultonV, et al.Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations. J Math Biol, 2016a;72(3):699–725.
HumphriesPJ, LinzS, SempleC. Cherry picking: A characterization of the temporal hybridization number for a set of phylogenies. Bull Math Biol, 2013a;75(10):1879–1890.
24.
HumphriesPJ, LinzS, SempleC. On the complexity of computing the temporal hybridization number for two phylogenies. Discrete Appl Math (1979), 2013b;161(7–8):871–880.
25.
HusonDH, RuppR, ScornavaccaC. Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press; 2010.
26.
HusonDH, ScornavaccaC. A survey of combinatorial methods for phylogenetic networks. Genome Biol Evol, 2011; 3:23–35.
27.
JanssenR, JonesM, MurakamiY. Combining networks using cherry picking sequences. In: International Conference on Algorithms for Computational Biology. Springer; 2020; pp. 77–92.
28.
JanssenR, MurakamiY. Linear time algorithm for tree-child network containment. In: International Conference on Algorithms for Computational Biology. Springer; 2020; pp. 93–107.
29.
JanssenR, MurakamiY. On cherry-picking and network containment. Theor Comput Sci, 2021; 856:121–150.
30.
KongS, PonsJC, KubatkoL, et al.Classes of explicit phylogenetic networks and their biological and mathematical significance. J Math Biol, 2022; 84(6):47.
31.
KooninE, MakarovaK, AravindL. Horizontal gene transfer in prokaryotes: Quantification and classification. Annu Rev Microbiol, 2001; 55(1):709–742.
32.
LandryK, TeodocioA, LafondM, et al.Defining phylogenetic network distances using cherry operations. IEEE/ACM Trans Comput Biol Bioinform, 2023a;20(3):1654–1666.
33.
LandryK, Tremblay-SavardO, LafondM. Finding agreement cherry-reduced subnetworks in level-1 networks. In: Comparative Genomics. (JahnK and VinařT. eds.) Springer Nature Switzerland: Cham; 2023b; pp. 179–195.
LandryK, Tremblay-SavardO, LafondM. A fixed-parameter tractable algorithm for finding agreement cherry-reduced subnetworks in level-1 orchard networks. J Comput Biol, 2024; 31(4):360–379.
36.
LinzS, SempleC. Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies. Adv Appl Math, 2019; 105:102–129.
37.
LiuB, RenC, KwakM, et al.Phylogenomic conflict analyses in the apple genus malus s.l. reveal widespread hybridization and allopolyploidy driving diversification, with insights into the complex biogeographic history in the northern hemisphere. J Integr Plant Biol, 2022; 64(5):1020–1043.
38.
LuB, ZhangL, LeongHW. A program to compute the soft Robinson–Foulds distance between phylogenetic networks. BMC Genomics, 2017; 18(Suppl 2):111.
39.
MooreGW, GoodmanM, BarnabasJ. An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets. J Theor Biol, 1973; 38(3):423–457.
40.
NakhlehL, RingeD, WarnowT. Perfect phylogenetic networks: A new methodology for reconstructing the evolutionary history of natural languages. Lan, 2005; 81(2):382–420.
