Search

Rooted phylogenetic networks are used by biologists to infer and represent complex evolutionary relationships between species that cannot be accurately explained by a phylogenetic tree. Tree-child networks are a particular class of rooted phylogenetic networks that has been extensively investigated in recent years. In this paper, we give a novel characterisation of a tree-child network $\mathcal{R}$ in terms of cherry-picking sequences that are sequences on the leaves of $\mathcal{R}$ and reduce it to a single vertex by repeatedly applying one of two reductions to its leaves. We show that our characterisation extends to unrooted tree-child networks which are mostly unexplored in the literature and, in turn, also offers a new approach to settling the computational complexity of deciding if an unrooted phylogenetic network can be oriented as a rooted tree-child network.

A normal network is uniquely determined by the set of phylogenetic trees that it displays. Given a set $\mathcal{P}$ of rooted binary phylogenetic trees, this paper presents a polynomial-time algorithm that reconstructs the unique binary normal network whose set of displayed binary trees is $\mathcal{P}$, if such a network exists. Additionally, we show that any two rooted phylogenetic trees can be displayed by a normal network and show that this result does not extend to more than two trees. This is in contrast to tree-child networks where it has been previously shown that any collection of rooted phylogenetic trees can be displayed by a tree-child network. Lastly, we introduce a type of cherry-picking sequence that characterises when a collection $\mathcal{P}$ of rooted phylogenetic trees can be displayed by a normal network and, further, characterise the minimum number of reticulations needed over all normal networks that display $\mathcal{P}$. We then exploit these sequences to show that, for all $n\ge 3$, there exist two rooted binary phylogenetic trees on $n$ leaves that can be displayed by a tree-child network with a single reticulation, but cannot be displayed by a normal network with less than $n-2$ reticulations.

In comparison to phylogenetic trees, phylogenetic networks are more suitable to represent complex evolutionary histories of species whose past includes reticulation such as hybridisation or lateral gene transfer. However, the reconstruction of phylogenetic networks remains challenging and computationally expensive due to their intricate structural properties. For example, the small parsimony problem that is solvable in polynomial time for phylogenetic trees, becomes NP-hard on phylogenetic networks under softwired and parental parsimony, even for a single binary character and structurally constrained networks. To calculate the parsimony score of a phylogenetic network $N$, these two parsimony notions consider different exponential-size sets of phylogenetic trees that can be extracted from $N$ and infer the minimum parsimony score over all trees in the set. In this paper, we ask: What is the maximum difference between the parsimony score of any phylogenetic tree that is contained in the set of considered trees and a phylogenetic tree whose parsimony score equates to the parsimony score of $N$? Given a gap-free sequence alignment of multi-state characters and a rooted binary level-$k$ phylogenetic network, we use the novel concept of an informative blob to show that this difference is bounded by $k+1$ times the softwired parsimony score of $N$. In particular, the difference is independent of the alignment length and the number of character states. We show that an analogous bound can be obtained for the softwired parsimony score of semi-directed networks, while under parental parsimony on the other hand, such a bound does not hold.

Recently, there has been a growing interest in the relationships between unrooted and rooted phylogenetic networks. In this context, a natural question to ask is if an unrooted phylogenetic network U can be oriented as a rooted phylogenetic network such that the latter satisfies certain structural properties. In a recent preprint, Bulteau et al. claim that it is computational hard to decide if U has a funneled (resp. funneled tree-child) orientation, for when the internal vertices of U have degree at most 5. Unfortunately, the proof of their funneled tree-child result appears to be incorrect. In this paper, we present a corrected proof and show that hardness remains for other popular classes of rooted phylogenetic networks such as funneled normal and funneled reticulation-visible. Additionally, our results hold regardless of whether U is rooted at an existing vertex or by subdividing an edge with the root.