Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees

Huber, Katharina, Linz, Simone and Moulton, Vincent (2025) Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees. Discrete Mathematics and Theoretical Computer Science. ISSN 1462-7264 (In Press)

Preview

PDF (main) - Accepted Version Available under License Creative Commons Attribution Non-commercial. Download (441kB) | Preview

Abstract

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 $\cN =(V,E)$ with leaf set $X$, for $X$ some set of species, in which every internal vertex in $\cN$ has degree three. One approach used to construct such phylogenetic networks is to take as input a collection $\cP$ of phylogenetic trees and to look for a network $\cN$ that contains each tree in $\cP$ and that minimizes the quantity $r(\cN) = |E|-(|V|-1)$ over all such networks. Such a network always exists, and the quantity $r(\cN)$ for an optimal network $\cN$ is called the {\em hybrid number of $\cP$}. In this paper, we give a new characterization for the hybrid number in case $\cP$ consists of two trees. This characterization is given in terms of a {\em 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 {\em 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 {\em tree bisection and reconnection distance} between the two trees, our new characterization also provides an alternative way to understand this important tree distance.

Item Type:	Article
Additional Information:	Data sharing statement: Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	LivePure Connector
Date Deposited:	12 May 2025 13:30
Last Modified:	12 May 2025 13:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/99241
DOI:	issn:1462-7264

Downloads

Actions (login required)

View Item