Katharina T. Huber ; Simone Linz ; Vincent Moulton - Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees

dmtcs:11633 - Discrete Mathematics & Theoretical Computer Science, May 20, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.11633
Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic treesArticle

Authors: Katharina T. Huber ; Simone Linz ; Vincent Moulton

    Phylogenetic networks are a special type of graph which generalize phylogenetic trees and that are used to model non-treelike evolutionary processes such as recombination and hybridization. In this paper, we consider {\em unrooted} phylogenetic networks, i.e. simple, connected graphs $\mathcal{N}=(V,E)$ with leaf set $X$, for $X$ some set of species, in which every internal vertex in $\mathcal{N}$ has degree three. One approach used to construct such phylogenetic networks is to take as input a collection $\mathcal{P}$ of phylogenetic trees and to look for a network $\mathcal{N}$ that contains each tree in $\mathcal{P}$ and that minimizes the quantity $r(\mathcal{N}) = |E|-(|V|-1)$ over all such networks. Such a network always exists, and the quantity $r(\mathcal{N})$ for an optimal network $\mathcal{N}$ is called the hybrid number of $\mathcal{P}$. In this paper, we give a new characterization for the hybrid number in case $\mathcal{P}$ consists of two trees. This characterization is given in terms of a cherry picking sequence for the two trees, although to prove that our characterization holds we need to define the sequence more generally for two forests. Cherry picking sequences have been intensively studied for collections of rooted phylogenetic trees, but our new sequences are the first variant of this concept that can be applied in the unrooted setting. Since the hybrid number of two trees is equal to the well-known tree bisection and reconnection distance between the two trees, our new characterization also provides an alternative way to understand this important tree distance.


    Volume: vol. 27:2
    Section: Graph Theory
    Published on: May 20, 2025
    Accepted on: May 8, 2025
    Submitted on: July 25, 2023
    Keywords: Mathematics - Combinatorics,Quantitative Biology - Populations and Evolution

    Consultation statistics

    This page has been seen 151 times.
    This article's PDF has been downloaded 161 times.