Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees
Preprint
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 $\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.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Classes of explicit phylogenetic networks and their biological and mathematical significanceJournal of Mathematical Biology, 2022
- A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary TreesAlgorithmica, 2022
- New Reduction Rules for the Tree Bisection and Reconnection DistanceAnnals of Combinatorics, 2020
- Deciding the existence of a cherry-picking sequence is hard on two treesDiscrete Applied Mathematics, 2019
- Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogeniesAdvances in Applied Mathematics, 2019
- On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network ProblemsAlgorithmica, 2017
- Folding and unfolding phylogenetic trees and networksJournal of Mathematical Biology, 2016
- Cherry Picking: A Characterization of the Temporal Hybridization Number for a Set of PhylogeniesBulletin of Mathematical Biology, 2013
- On the complexity of computing the temporal hybridization number for two phylogeniesDiscrete Applied Mathematics, 2013
- Subtree Transfer Operations and Their Induced Metrics on Evolutionary TreesAnnals of Combinatorics, 2001