# Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal
arcs

Katharina T. Huber and Liam J. Maher  School of Computing Sciences, University
of East Anglia, Norwich, UK<EMAIL_ADDRESS>School of Computing Sciences,
University of East Anglia, Norwich, UK<EMAIL_ADDRESS>
###### Abstract.

Polyploidization is an evolutionary process by which a species acquires
multiple copies of its complete set of chromosomes. The reticulate nature of
the signal left behind by it means that phylogenetic networks offer themselves
as a framework to reconstruct the evolutionary past of species affected by it.
The main strategy for doing this is to first construct a so called multiple-
labelled tree and to then somehow derive such a network from it. The following
question therefore arises: How much can be said about that past if such a tree
is not readily available? By viewing a polyploid dataset as a certain vector
which we call a ploidy (level) profile we show that, among other results,
there always exists a phylogenetic network in the form of a beaded
phylogenetic tree with additional arcs that realizes a given ploidy profile.
Intriguingly, the two end vertices of almost all of these additional arcs can
be interpreted as having co-existed in time thereby adding biological realism
to our network, a feature that is, in general, not enjoyed by phylogenetic
networks. In addition, we show that our network may be viewed as a generator
of ploidy profile space, a novel concept similar to phylogenetic tree space
that we introduce to be able to compare phylogenetic networks that realize one
and the same ploidy profile. We illustrate our findings in terms of a publicly
available Viola dataset.

##  1\. Introduction

Polyploidization is an evolutionary phenomenon thought to be one of the key
players in plant evolution. It has, however, also been observed in fish [22],
and fungi [1] and arises when a species acquires multiple copies of its full
set of chromosomes. This can be the result of, for example, a species
undergoing whole genome duplication (autopolyploidization) or through
acquisition of a further complete set of chromosomes via interbreeding with a
different, usually closely related, species (allopolyploidization) [1] (see
also [5] who point out that the definitions of allopolyploidy and
autopolyploidy are controversial). Examples of autopolyploids include crop
potato [34] and bananas and watermelon [38] and examples of allopolyploids
include bread wheat [25] and oilseed rape. Understanding better how polyploids
have arisen (and still arise) therefore has potentially far reaching
consequences.

Many tools for shedding light into the evolutionary past of a polyploid data
set such as PADRE [23] and AlloPPnet [20] start with a multiple-labelled tree,
sometimes also called a MUL-tree or a multi-labelled tree.

Figure 1.  (i) One of potentially many phylogenetic networks that realize the
ploidy levels $14,12,12,10$ of a set $X=\\{x_{1},x_{2},x_{3},x_{4}\\}$ of taxa
where $14$ is the ploidy level of $x_{1}$, the ploidy level of $x_{2}$ and
$x_{3}$ is $12$, respectively and the ploidy level of $x_{4}$ is $10$. To
improve clarity of exposition, we always assume that unless indicated
otherwise, arcs are directed away from the root (which is always at the top).
(ii) The network in (i) represented in such a way that every reticulation
vertex (indicated throughout the paper by a square and defined below) has
precisely one incoming horizontal arc implying that the end vertices of such
an arc represent ancestral species that have existed at the same point in
time. In both (i) and (ii) the phylogenetic network resulting from deleting
the dashed bead and its dashed outgoing arc realizes the ploidy profile
$\vec{m}=(7,6,6,5)$.

These types of trees differ from the standard phylogenetic trees by allowing
two or more leaves to be labelled with the same species. In the case of PADRE
a (phylogenetic) network is then produced from such a tree by folding it up as
described in, for example, [14]. Referring the interested reader to Figure
1(i) for an example and below for definitions, it suffices to say at this
stage that a phylogenetic network is a directed graph with leaf set a set of
taxa (e.g. species) of interest, a single root (usually drawn at the top), and
no directed cycles. Note that to be able to account for autopolyploidy, we
deviate from the standard definition of a phylogenetic network (see e. g.
[33]) by also allowing it to contain beads, that is, pairs of parallel arcs,
as is the case in the networks depicted in Figure 1. Polyploidization events
are represented in such networks as reticulation vertices, that is, vertices
with more than one arc coming into them. For clarity of exposition, we
indicate reticulation vertices throughout the paper in terms of squares.
Although PADRE is generally fast and not constrained by an upper limit on the
ploidy levels in a dataset of interest, its underlying assumptions imply that
it is highly susceptible to noise in the multiple-labelled tree from which the
network is constructed. In the case of AlloPPnet, a phylogenetic network is
inferred using, among other techniques, the multispecies coalescent to account
for incomplete lineage sorting. The computational demands of AlloPPnet however
mean that it can only be applied on relatively small data sets that contain
only diploids and tetraploids [29].

One approach to obtain an input multiple-labelled tree for PADRE is to try and
construct it as a consensus multiple-labelled tree from a set of multiple-
labelled gene trees. This task is relatively straight-forward for phylogenetic
trees by applying, for example, some kind of consensus approach to the
collection of clusters induced by the trees. The corresponding approach for
constructing a consensus multiple-labelled tree from a collection of multiple-
labelled gene trees however gives rise to a computationally hard decision
problem [10]. A consensus multiple-labelled tree might therefore not always be
readily available for a dataset. The following question therefore arises: How
much can we say about the reticulate evolutionary past of a polyploid dataset
if a multiple-labelled tree is not readily available? Since one of the
signatures left by polyploidization is the ploidy level of a species (i. e.
the number of copies of the complete set of chromosomes of that species), we
address this question in terms of a dataset’s ploidy levels or more precisely
the ploidy levels of the taxa that make up the dataset using phylogenetic
networks as a framework. Interpreting the ploidy level of a species as the
number of directed paths from the root of a phylogenetic network $N$ to the
leaf in $N$ that represents that species, Figure 1(i) implies that, in
general, ploidy levels do not preserve the topology of the phylogenetic
network that induced them. For example, swapping $x_{2}$ with $x_{3}$ in that
network results in a phylogenetic network that induces the same ploidy levels
on $\\{x_{1},\ldots,x_{4}\\}$ as the network pictured in Figure 1(i). We are
therefore interested in understanding to what extent a phylogenetic network
representing the evolutionary past of a polyploid dataset can be derived
solely from the ploidy levels of the species that make up the dataset.

Note that since polyploidization events are assumed to be rare, we are
particularly interested in phylogenetic networks that enjoy this property and
also aim to minimize the number of reticulation vertices. From the perspective
of reducing the complexity of our mathematical arguments this immediately
implies that we may assume the ploidy level of a taxon to not be even. Indeed,
if we have a dataset where every ploidy level is of the form $m=2m^{\prime}$,
some positive integer $m^{\prime}$, then since polyploidization events are
assumed to be rare, we may assume the last common ancestor of the dataset’s
taxa to have undergone autopolyploidization. The root of a phylogenetic
network $N$ that represents the evolutionary past of the dataset is therefore
contained in a bead and that bead accounts for the factor $2$ in $m$. Thus,
the phylogenetic network obtained by removing this bead and the arc that joins
it to the rest of $N$ is a phylogenetic network that represents the factor
$m^{\prime}$ of $m$ in terms of numbers of directed paths from the root to the
leaves.

In view of the above, we call any (finite) vector of positive integers that is
indexed by a (finite, non-empty) set $X$ a ploidy profile (on $X$). Although
related to the recently introduced ancestral profiles [7] (but also see [2])
ploidy profiles differ from them by only recording the number of directed
paths from the root of a phylogenetic network $N$ to every leaf of $N$.
Ancestral profiles on the other hand record the number of directed paths from
every non-leaf vertex in $N$ to all the leaves below that vertex. In
particular, a ploidy profile is an element of an ancestral profile of a
phylogenetic network.

To help motivate our approach for addressing our question, consider the
phylogenetic network $N$ with leaf set $X=\\{x_{1},x_{2},x_{3},x_{4}\\}$
depicted in Figure 1(i) where the square vertices at the end of each pair of
two parallel arcs represent autopolyploidization and the remaining four square
vertices represent allopolyploidization. Then taking for each taxon $x$ in $X$
the number of directed paths from the root of the network to $x$ results in
the ploidy profile $\vec{m}=(14,12,12,10)$ where the first component is
indexed by $x_{1}$, the second by $x_{2}$ and so on. Each component in
$\vec{m}$ is of the form $2m$, some positive integer $m$, and the phylogenetic
network rooted at $r$ obtained by removing the dashed bead together with the
dashed arc coming into $r$ represents the ploidy profile
$\vec{m^{\prime}}=(7,6,6,5)$ in terms of numbers of directed paths from $r$ to
the leaves. With this in mind, we say that a ploidy profile
$\vec{m}=(m_{1},\ldots,m_{n})$, $n\geq 1$ on $X=\\{x_{1},\ldots,x_{n}\\}$ is
realized by a phylogenetic network $N$ with leaf set $X$ if, for all $1\leq
i\leq n$, the number of directed paths from the root of $N$ to $x_{i}$ is
$m_{i}$. For example, both phylogenetic networks pictured in Figure 1 realize
the ploidy profile $\vec{m}=(14,12,12,10)$ indexed by
$X=\\{x_{1},x_{2},x_{3},x_{4}\\}$.

Contributing to the emerging field of Polyploid Phylogenetics [29], a first
inroad into our question was made in [11] by studying the hybrid number of a
ploidy profile $\vec{m}$, that is, the minimal number of polyploidization
events required by a phylogenetic network to realize $\vec{m}$. As it turns
out, the arguments underlying the results in [11] largely rely on a certain
iteratively constructed network that realizes $\vec{m}$. Denoting for a choice
$C$ of initializing network the generated network by
$N(\vec{m})=N_{C}(\vec{m})$ and changing the network initializing that
construction in a way that does not affect the main findings in [11] (see
below for details), we show that even more can be said about ploidy profiles.
For example, our first result (Proposition 4.1) shows that $N(\vec{m})$ may be
thought of as a generator of ploidy profile space (defined in a similar way as
phylogenetic tree space) in the sense that any realization of $\vec{m}$ can be
reached from $N(\vec{m})$ via a number of multiple-labelled tree editing
operations and reticulation vertex splitting operations. As an immediate
consequence of this we obtain a distance measure for phylogenetic networks
that realize one and the same ploidy profile. On a more speculative level it
might be interesting to see if $N(\vec{m})$ lends itself as a useful prior for
a Bayesian method along the lines as described in [35].

Our second result (Theorem 6.1) shows that a key concept introduced in [11]
called the simplification sequence of a ploidy profile $\vec{m}$ is in fact
closely related to the notion of a cherry reduction sequence [7] for
$N(\vec{m})$, also called a cherry picking sequence in [19]. In case
autopolyploidy is not suspected to have played a role in the evolution of a
dataset, this implies that the network $N(\vec{m})$ can also be reconstructed
from phylogenetic networks on three leaves called trinets [32]. These can be
obtained from a dataset using, for example, the TriLoNet software [26].

Exemplified in terms of the phylogenetic network depicted in Figure 1(ii) for
the ploidy profile $(14,12,12,10)$, our third result (Theorem 6.2) implies
that for any ploidy profile we can always find a phylogenetic network
realizing it in the form of a phylogenetic tree that potentially contains
beads to which additional arcs have been added and at most one of those arcs
is not horizontal. In the context of this it is important to note that, in
general, a phylogenetic network cannot be thought of as a phylogenetic tree
with additional arcs let alone horizontal ones. The reason for this is that
horizontal arcs imply that the ancestral taxa joined by such an arc must have
existed at the same time (see also [33, Section 10.3.3] for more on this and
the Viola dataset below for an example).

The remainder of the paper is organized as follows. In the next section, we
review relevant basic terminology surrounding graphs, phylogenetic networks
and ploidy profiles. For a ploidy profile $\vec{m}$, we outline the
construction of the network $N(\vec{m})$ in Section 3. This includes the
definition of the simplification sequence for $\vec{m}$. Subsequent to this,
we introduce ploidy profile space in Section 4 and also establish Proposition
4.1 in that section. Sections 6 is concerned with establishing Theorems 6.1
and 6.2. To do this, we use Theorem 5.1 which we establish in Section 5. That
theorem is underpinned by the concept of a so called HGT-consistent labelling
introduced in [37], a notion that we extend to our types of phylogenetic
networks here. In the last but one section, we employ a simplified version of
a Viola dataset from [24] to help explain our findings within the context of a
real biological dataset. We conclude with some potential directions of further
research in the last section.

##  2\. Preliminaries

We start with introducing basic concepts surrounding phylogenetic networks.
Throughout the paper, we assume that $X$ is a (finite) set that contains at
least one element. Also, we denote the number of elements in $X$ by $n$.

###  2.1. Graphs

Suppose for the following that $G$ is a directed acyclic graph with a single
root which might contain parallel arcs but no loops. We denote an arc starting
at a vertex $u$ and ending in a vertex $v$ by $(u,v)$. If there exist two arcs
from $u$ to $v$ then we refer to the pair of arcs from $u$ to $v$ as a bead of
$G$.

Suppose $v$ is a vertex of $G$. Then we refer to the number of arcs coming
into $v$ as the indegree of $v$ in $G$ and denote it by $indeg(v)$. Similarly,
we call the number of outgoing arcs of $v$ the outdegree of $v$ in $G$ and
denote it by $outdeg(v)$. We call $v$ the root of $G$, if $indeg(v)=0$, and we
call $v$ a leaf of $G$ if $indeg(v)=1$ and $outdeg(v)=0$. We denote the set of
vertices of $G$ by $V(G)$ and the set of leaves of $G$ by $L(G)$. We call $v$
a tree vertex if $outdeg(v)=2$ and $indeg(v)=1$, and we call $v$ a
reticulation vertex if $indeg(v)=2$ and $outdeg(v)=1$. If $w$ is also a vertex
in $G$ then we say that $w$ is below $v$ if either $v=w$ or there exists a
directed path from the root of $G$ to $w$ that crosses $v$. If $w$ is below
$v$ and $v\not=w$ then we say that $w$ is strictly below $v$. A parent of a
vertex $v$ is the vertex connected to $v$ on the path to the root. A child of
a vertex $v$ is a vertex of which $v$ is the parent.

Suppose $a$ and $b$ are two distinct leaves of $G$. Then the set $\\{a,b\\}$
is called a cherry of $G$ if the parent $p_{a}$ of $a$ is also the parent of
$b$. If the parent $p_{b}$ of $b$ is a reticulation vertex and there is an arc
$(p_{a},p_{b})$ from $p_{a}$ to $p_{b}$ then the set $\\{a,b\\}$ is called a
reticulate cherry. In this case, the arc $(p_{a},p_{b})$ is called a
reticulation arc of $G$ and the leaf $b$ is called a reticulation leaf of $G$.

For example, $x_{1}$ is the reticulate leaf of the reticulate cherry
$\\{x_{1},x_{2}\\}$ in the graph depicted in Figure 1(i). The parent of
$x_{2}$ is a tree vertex and the parent of $x_{1}$ is a reticulation vertex.
The vertices $u$ and $v$ form a bead.

###  2.2. Phylogenetic networks and trees

Suppose $G$ is a graph as described above. If $G$ contains at least three
vertices then we call $G$ a (phylogenetic) network (on $X$) if the outdegree
of the root $\rho$ of $G$ is 2, the leaf set of $G$ is $X$, and every vertex
other than $\rho$ or a leaf is a tree vertex or a reticulation vertex. Note
that our definition of a phylogenetic network differs from the standard
definition of such an object (see e.g. [33]) by allowing the network to
contain beads and $X$ to contain a single element. To distinguish between our
type of phylogenetic networks and the standard type of phylogenetic networks
we refer to the latter as beadless phylogenetic networks. We call a
phylogenetic network (on $X$) a phylogenetic tree (on $X$) if it does not
contain any reticulation vertices.

Finally, we call a phylogenetic network $N$ on $X$ such that $N$ is either a
phylogenetic tree on $X$ or every reticulation vertex of $N$ is contained in a
bead a beaded tree (see e.g. [36] and [9] for more on such graphs).

###  2.3. Ploidy profiles

Let $X=\\{x_{1},\ldots,x_{n}\\}$. Then, as mentioned in the introduction, a
ploidy profile $\vec{m}=(m_{1},\ldots,m_{n})$ (on $X$) is an $n$-dimensional
vector of positive integers such that each component is indexed by an element
in $X$. For ease of readability, we will assume from now on that the elements
in $X$ are always ordered in such a way that $x_{i}$ indexes component $m_{i}$
of $\vec{m}$, for all $1\leq i\leq n$, and that $\vec{m}$ is in descending
order, that is, $m_{i}\geq m_{i+1}$ holds for all $1\leq i\leq n-1$. For
example the vector $\vec{m}=(7,6,6,5)$ is a ploidy profile on
$X=\\{x_{1},x_{2}.x_{3},x_{4}\\}$ where $x_{1}$ indexes the first component i.
e. $7$, $x_{2}$ indexes the second component, and so on.

Suppose $\vec{m}=(m_{1},\ldots,m_{n})$ is a ploidy profile on $X$. If
$m_{1}\geq 2$ and all other components of $\vec{m}$ are 1 then we call
$\vec{m}$ a simple ploidy profile. If $\vec{m}$ is a simple ploidy profile and
$n=1$ then we call $\vec{m}$ a strictly simple ploidy profile. Finally, we say
that a phylogenetic network is a realization of $\vec{m}$ if it realizes
$\vec{m}$ (as defined in the introduction). For example, the ploidy profile
$\vec{m}=(77,1,1,1)$ is simple but not strictly simple and the ploidy profile
$(77)$ is strictly simple. The phylogenetic networks depicted in Figure 1 are
realizations of the ploidy profile $\vec{m}=(14,12,12,10)$.

##  3\. Realizing ploidy profiles

We start this section by introducing further terminology which will allow us
to construct our network $N(\vec{m})$ from a ploidy profile $\vec{m}$. To
avoid undesirable uniqueness issues, we remark that our construction is
slightly different from the construction of the corresponding network for
$\vec{m}$ introduced in [11] in that we choose a different network with which
we initialize its construction. As part of our construction we also include a
worked example at the end of this section.

Suppose $\vec{m}=(m_{1},m_{2},\ldots,m_{n})$ is a ploidy profile on
$X=\\{x_{1},x_{2},\ldots,x_{n}\\}$. Then we first construct a sequence
$\sigma(\vec{m})$ of ploidy profiles from $\vec{m}$ which we call the
simplification sequence for $\vec{m}$. This sequence starts with the ploidy
profile $\vec{m}$ and terminates with a certain simple ploidy profile
$\vec{m_{t}}$ which we call the terminal element of $\sigma(\vec{m})$. If
$\vec{m}$ is simple, then we define $\sigma(\vec{m})$ to contain only
$\vec{m}$. Thus, $\vec{m}=\vec{m_{t}}$ in this case.

Assume for the following that $\vec{m}$ is not simple. To define
$\sigma(\vec{m})$ in this case, assume furthermore that all ploidy profiles in
$\sigma(\vec{m})$ have been constructed already up to and including a ploidy
profile $\vec{m^{\prime}}=(m_{1}^{\prime},\ldots,m_{q}^{\prime})$ on some set
$X^{\prime}=\\{x_{1}^{\prime},\ldots,x_{q}^{\prime}\\}$, some $q\geq 1$. If
$\vec{m^{\prime}}$ is simple then we define $\vec{m^{\prime}}$ to be
$\vec{m_{t}}$. So assume that $\vec{m^{\prime}}\not=\vec{m_{t}}$. Put
$\alpha=m_{1}^{\prime}-m_{2}^{\prime}$. Let $X^{\prime\prime}$ denote the set
that indexes the next ploidy profile in $\sigma(\vec{m})$ which we call
$\vec{m^{\prime\prime}}$. Then $\vec{m^{\prime\prime}}$ and $X^{\prime\prime}$
are obtained from $\vec{m^{\prime}}$ and $X^{\prime}$ by applying one of the
following cases.

  1. $\bullet$

If $\alpha=0$ then delete $m_{1}^{\prime}$ from $\vec{m^{\prime}}$ and its
index $x_{1}^{\prime}$ from $X^{\prime}$. To obtain $X^{\prime\prime}$, rename
the elements $x_{k}^{\prime}$ as $x_{k-1}^{\prime\prime}$, $2\leq k\leq q$.

  2. $\bullet$

If $\alpha>m_{2}^{\prime}$ then replace $m_{1}^{\prime}$ by $\alpha$. The set
$X^{\prime\prime}$ is $X^{\prime}$ in this case and the indexing of the
components of $\vec{m^{\prime\prime}}$ is as in $\vec{m^{\prime}}$.

  3. $\bullet$

If $\alpha\leq m_{2}^{\prime}$ then remove $m^{\prime}_{1}$ from
$\vec{m^{\prime}}$ and its index $x_{1}^{\prime}$ from $X^{\prime}$ to obtain
a ploidy profile $\vec{a}$ on $X^{\prime}-\\{x^{\prime}_{1}\\}$. Into
$\vec{a}$, insert $\alpha$ so that the resulting integer vector $\vec{b}$ is a
ploidy profile on
$X^{\prime\prime}=X^{\prime}-\\{x^{\prime}_{1}\\}\cup\\{x\\}$ where $x$ is an
element not already contained in $X^{\prime}$. That element is used to index
$\alpha$ in $\vec{b}$. As $\vec{a}$ might already contain a component with
value $\alpha$, we also require that $\alpha$ is inserted into $\vec{a}$
directly after the last occurrence of $\alpha$ to ensure that $\vec{b}$ is
unique. Next, relabel the elements in $X^{\prime\prime}$ so that the indexing
of $\vec{b}$ conforms to our indexing convention for ploidy profiles. Finally,
put $\vec{m^{\prime\prime}}=\vec{b}$.

This completes the construction of the simplification sequence for $\vec{m}$.
To aid intuition, we present the simplification sequence for the ploidy
profile $\vec{m}=(7,6,6,5)$ at the end of this section.

To obtain our realization for our ploidy profile $\vec{m}$, we next choose a
core network for $\vec{m}$, that is, a phylogenetic network $N$ that realizes
the terminal element $\vec{m_{t}}$. This is always possible since for any
simple ploidy profile $(m_{1},\ldots,m_{n})$ on $X=\\{x_{1},\ldots,x_{n}\\}$
such a network can be obtained using the following naive approach. Take a
directed path $P$ with $n+2(m_{1}-1)$ vertices and label the first $m_{1}-1$
vertices on $P$ by $v_{i}$, $1\leq i\leq m_{1}-1$ and the next $n-1$ vertices
by $w_{i}$, $2\leq i\leq n$. Starting at the other end of $P$, label the first
vertex $x_{1}$ and the remaining $m_{1}-1$ vertices by $v_{i}^{\prime}$,
$1\leq i\leq m_{1}-1$. Finally, for all $2\leq i\leq n$ attach the arc
$(w_{i},x_{i})$ and, for all $1\leq i\leq m_{1}-1$, the arc
$(v_{i},v_{i}^{\prime})$. By construction, the resulting graph is a
phylogenetic network (without horizontal arcs) that realizes $\vec{m_{t}}$. To
keep the description of the construction of $N(\vec{m})$ from $N(\vec{m_{t}})$
compact, we refer the interested reader to Section 5 for the construction of a
more attractive choice of core network for $\vec{m}$.

Starting with a core network $N$ for $\vec{m}$ we then apply a traceback
through $\sigma(\vec{m})$ to obtain $N(\vec{m})$ via the addition of vertices
and arcs (see e. g. [19], where, in a different context, this process was
called “adding” vertices). For this we distinguish the same cases as before.
More precisely, if $\vec{m}$ is simple and therefore the terminal element of
$\sigma(\vec{m})$, we define $N(\vec{m})$ to be $N$. So assume that $\vec{m}$
is not simple and that, starting at $\vec{m_{t}}$, for all ploidy profiles in
$\sigma(\vec{m})$ up to and including a ploidy profile
$\vec{m^{\prime\prime}}$ on $X^{\prime\prime}$ a realization of them has
already been constructed. Let $N^{\prime\prime}$ denote the realization
obtained for $\vec{m^{\prime\prime}}$. As before, let $\vec{m^{\prime}}$ on
$X^{\prime}$ denote the ploidy profile in $\sigma(\vec{m})$ that precedes
$\vec{m^{\prime\prime}}$. For clarity of presentation of the main ideas, we
remark that in each of the following cases the set $X^{\prime}$ is obtained
from $X^{\prime\prime}$ by reversing the indexing that formed part of the
corresponding case in the construction of $\sigma(\vec{m})$.

  1. $\bullet$

If $\alpha=0$ then replace $x_{1}^{\prime\prime}$ by the cherry
$\\{x_{1}^{\prime},x_{2}^{\prime}\\}$.

  2. $\bullet$

If $\alpha>m_{2}$, then subdivide the incoming arc of $x_{1}^{\prime\prime}$
by a new vertex $u$. Next, subdivide the incoming arc of
$x_{2}^{\prime\prime}$ by a vertex $v$ and add the new arc $(v,u)$.

  3. $\bullet$

If $\alpha\leq m_{2}$ then let $\vec{a}$ and $\vec{b}$ as in the corresponding
case of the construction of $\sigma(\vec{m})$. Let $j$ denote the index of the
component of $\vec{b}$ that was inserted into $\vec{a}$ as part of the
construction of $\vec{b}$. Then subdivide the incoming arc of
$x_{j}^{\prime\prime}$ by a new vertex $v$ and replace $x_{1}^{\prime\prime}$
by the cherry $\\{x_{1}^{\prime},x_{2}^{\prime}\\}$. Next, subdivide the
incoming arc of $x_{1}^{\prime}$ by a new vertex $u$. Finally, add the arc
$(v,u)$ and delete $x_{j}^{\prime\prime}$ and its incoming arc
$(u,x_{j}^{\prime\prime})$ (suppressing the resulting indegree and outdegree
one vertex).

To illustrate the construction of $N(\vec{m})$, consider the ploidy profile
$\vec{m}=(7,6,6,5)$ on $X=\\{x_{1},x_{2},x_{3},x_{4}\\}$. Then the sequence
$\vec{m}$, $(6,6,5,1)$, $(6,5,1)$ $(5,1,1)$ is the simplification sequence
$\sigma(\vec{m})$ for $\vec{m}$. Since $\vec{m_{t}}=(5,1,1)$, the phylogenetic
network depicted on the left of Figure 2 is a core network for $\vec{m}$. In
fact it is the core network $\mathcal{B}(\vec{m})$ for $\vec{m}$ whose
construction is described in the proof of Theorem 5.1. The network $N_{0}$ on
the right of Figure 2 is the network $N(\vec{m})$ when initializing its
construction with $\mathcal{B}(\vec{m})$. It is obtained via the traceback of
$\sigma(\vec{m})$ by applying the cases indicated below the arrows. To be able
to reuse the example to help illustrate Theorem 5.1, we represent one of the
incoming arcs of each of the reticulation vertices of the networks that make
up the figure as a thin, horizontal arc. Note that the leaf labels between the
networks do not necessarily translate between the networks due to the applied
renaming scheme for the elements of the indexing sets.

Figure 2. When reading from left to right, the construction of $N(\vec{m})$
obtained from the traceback through the simplification sequence
$\sigma(\vec{m})$ for the ploidy profile $\vec{m}=(7,6,6,5)$ on
$\\{x_{1},\ldots,x_{4}\\}$. The ploidy profiles that make up $\sigma(\vec{m})$
are given at the bottom. The terminal element $\vec{m_{t}}$ of
$\sigma(\vec{m})$ is the ploidy profile $(5,1,1)$ and the phylogenetic network
$\mathcal{B}(\vec{m})$ on the left is a core network for $\vec{m}$. The cases
that apply in each step of the traceback are indicated below the arrows
between the four ploidy profiles that make up $\sigma(\vec{m})$. The thin
horizontal arcs relate to the example illustrating Theorem 5.1.

We conclude this section by remarking that, by [11, Theorem 2], $N(\vec{m})$
employs the minimum number of reticulation vertices to realize $\vec{m}$
provided (i) $\mathcal{B}(\vec{m})$ uses the minimum number of reticulation
vertices to realize the terminal element of the simplification sequence of
$\vec{m}$, and (ii) the case $\alpha>m_{2}^{\prime}$ is never executed when
constructing $N(\vec{m})$ from $\mathcal{B}(\vec{m})$ where $\alpha$ and
$m_{2}^{\prime}$ are as in the description of that case (see Figures 6 and 10
in [11] for more on this and the next section for an example).

##  4\. Comparing realizations of one and the same ploidy profile

As indicated in the previous section, a ploidy profile $\vec{m}$ might have
more than one core network. This immediately begs the question of how
different realizations of a ploidy profile might be. For phylogenetic trees
and, more recently, for general rooted (beadless) or unrooted phylogenetic
networks this type of question has generally been addressed in the form of
understanding their space. From a formal point of view, this space which is
called tree space in the case of phylogentic trees and network space in the
case of rooted (beadless) or unrooted phylogenetic networks is a graph.
Calling that graph $G$ then the vertices of $G$ are the phylogenetic trees or
networks of interest and any two vertices of $G$ are joined by an edge if one
can be transformed into the other using some graph-editing operation such as
the Subtree Prune and Regraft operation (SPR) for phylogenetic trees [31] or
one the operations described in [6, 13, 18, 35].

None of the operations described in those papers however preserve, in general,
our central requirement that a network is a realization of a ploidy profile.
For technical reasons which will allow us to extend the idea of tree/network
space to a space of ploidy profiles, we first need to extend the notion of a
phylogenetic network. To this end, we call a phylogenetic network where
different leaves are allowed to share the same label a multiple-labelled
network. In the form of, for example, multiple-labelled trees such structures
have already been used successfully in a polyploidization context [27, 29].
For their usage in a more mathematical context see e. g. [15] and the
references therein. For example, consider the phylogenetic network depicted in
Figure 4(ii). Then the graph obtained as follows is a multiple-labelled
network. First, remove the arc $(w,s_{4}^{\prime})$ and one of the incoming
arcs of $h_{6}$. Next, suppress $h_{6}$ and its parent and add two further
vertices both of which we call $x_{1}$. Finally, add an arc $(w,x_{1})$ that
ends in one of the two new vertices $x_{1}$ and an arc
$(s_{4}^{\prime},x_{1})$ that ends in the other so that a cherry on the
multiset $\\{x_{1},x_{1}\\}$ is generated. Since the number of directed paths
from the root of the resulting graph to each of its leaves is not affected by
this process, we extend the definitions of a reticulation vertex and when a
ploidy profile is realized by a phylogenetic network to multiple-labelled
networks in the obvious way.

Armed with this, we are now ready to define ploidy profile space. Suppose
$\vec{m}$ is a ploidy profile on $X$. Then we refer to the following graph as
ploidy profile space $\mathcal{P}(\vec{m})$ for $\vec{m}$. The vertex set of
the graph is the set of all multiple-labelled networks that realize $\vec{m}$.
To be able to define the edge set of our graph, we require a further concept.
We say that a multiple-labelled network $N^{\prime}$ is obtained from a
multiple-labelled network $N$ via a split operation if there exists a
reticulation vertex $h$ of $N$ with parents $p_{1}$ and $p_{2}$ and child $c$
such that $(h,c)$ is a cut-arc and $N^{\prime}$ is obtained from $N$ as
follows. First delete $h$ and its three incident arcs from $N$ and then make a
copy of the subgraph of $N$ induced by the vertices of $N$ below $c$. Finally,
add the arc $(p_{2},c)$ as the incoming arc to one of the two copies of $c$
and $(p_{1},c)$ as the incoming arc of the other. We illustrate this operation
in Figure 3.

Figure 3. An illustration of the split operation applied to the reticulation
vertex $h$ with parents $p_{1}$ and $p_{2}$ and child $c$. $N_{1}$ and $N_{2}$
indicate parts of the multiple-labelled networks $N$ and $N^{\prime}$ that are
of no relevance to the discussion.

Informally speaking, the split operation may be thought of as “un-zipping” a
multiple-labelled network (see also [28] for a related notion of “unzipping” a
phylogenetic network). Choose an edit distance for comparing multiple-labelled
trees that realize $\vec{m}$ such that the following graph is connected. The
vertex set is the set of all multiple-labelled trees that realize $\vec{m}$
and any two multiple-labelled trees in that set are joined by an edge if their
distance under the chosen edit distance is 1. For our next result (Proposition
4.1), we are interested in edit distances for which this space is connected
(see [16] for examples of such distances and also [21] for some recent
computational complexity results concerning them).

Armed with the split operation and choice of edit distance, we continue our
definition of ploidy profile space for $\vec{m}$ as follows. We say that two
distinct realizations $N$ and $N^{\prime}$ of $\vec{m}$ are joined by an edge
if either $N^{\prime}$ can be obtained from $N$ via a single split operation
or $N$ and $N^{\prime}$ are both multiple-labelled trees and their distance
under the chosen edit distance is 1.

######  Proposition 4.1.

For any ploidy profile $\vec{m}$ on $X$ and any edit distance on the set of
multiple-labelled trees realizing $\vec{m}$ such that the associated space of
multiple-labelled trees is connected, ploidy profile space
$\mathcal{P}(\vec{m})$ is connected.

###### Proof.

Choose an edit distance $D$ such that the associated space of multiple-
labelled trees realizing $\vec{m}$ is connected. Clearly, any realization $N$
of $\vec{m}$ can be transformed into a realization $N^{+}$ of $\vec{m}$ that
does not contain reticulation vertices that are above each other using a
sequence of split operations. Since the vertex set of ploidy profile space is
the set of multiple-labelled phylogenetic networks that realize $\vec{m}$, it
follows that $N^{+}$ can be transformed into a multiple-labelled tree that
realizes $\vec{m}$ by using a further sequence of split operations. By
assumption on $D$, any multiple-labelled tree that realizes $\vec{m}$ can be
transformed into another multiple-labelled tree which also realizes $\vec{m}$
via a sequence $\chi$ of multiple-labelled trees that all realize $\vec{m}$,
such that any two consecutive multiple-labelled trees in $\chi$ have distance
1 under $D$. Hence,  $\mathcal{P}(\vec{m})$ is connected. $\Box$

∎

As an immediate consequence of Proposition 4.1, we obtain a distance measure
for realizations of a ploidy profile $\vec{m}$. More precisely, choose an edit
distance $D$ for comparing two multiple-labelled trees that realize $\vec{m}$
such that the space associated to $D$ is connected. Then we define the
distance $D_{\mathcal{P}(\vec{m})}(N,N^{\prime})$ of any two realizations $N$
and $N^{\prime}$ of $\vec{m}$ to be the length of a shortest path in
$\mathcal{P}(\vec{m})$ that joins $N$ and $N^{\prime}$. We refer the
interested reader to Section 7 for an example where we compute an upper bound
on this distance for a real biological dataset.

##  5\. A core network with horizontal arcs

Although undoubtedly useful, phylogenetic networks on their own do not provide
information as to whether or not two species suspected of hybridization have
existed at the same point in time. To add this type of realism to phylogenetic
networks, so called time stamp maps can be used. Subject to some constraints
such maps assign a non-negative real number to every vertex of a phylogenetic
network (see e. g. [3, 8, 37]). As is well-known, not every phylogenetic
network admits a time stamp map. However those that do enjoy the attractive
property that arcs whose both end vertices have been assigned the same time
stamp can be drawn horizontally to indicate that the ancestral species
represented by their end vertices have existed at the same time.

To be able to extend the notion of a time stamp map to ploidy profiles, we
start with the definition of a certain time stamp map for (beadless)
phylogenetic networks that originally appeared in [37]. Suppose that $N$ is a
beadless phylogenetic network on a set $X$ with at least two elements. Then a
map $t:V(N)\to\mathbb{R}_{\geq 0}$ is called a HGT-consistent labelling of $N$
if the following properties hold:

  1. (P1)

For all arcs $(u,v)$ of $N$, we have that $t(u)\leq t(v)$ if $v$ is a
reticulation vertex and, otherwise, that $t(u)<t(v)$.

  2. (P2)

For each vertex $u$ that is not a leaf of $N$ there exists a child $v$ such
that $t(u)<t(v)$.

  3. (P3)

For each reticulation vertex $v$ of $N$ there exists precisely one parent $u$
such that $t(v)=t(u)$.

Informally speaking, Property (P1) means that time is moving forward, from the
root of the network to its leaves. Property (P2) implies that every ancestral
species $v$ has given rise to at least one species that did not exist at the
same time as $v$. Finally, Property (P3) implies for every reticulation vertex
$v$ that the ancestral species represented by $u$ must have existed at the
same time as the species represented by $v$. Examples of (beadless)
phylogenetic networks that admit a HGT–consistent labelling include stackfree
phylogenetic networks, that is, (beadless) phylogenetic networks that have no
arcs for which both end vertices are reticulation vertices (see [2] for more
on such networks). It should however be noted that there exist (beadless)
phylogenetic networks that admit such a labelling which might not be
stackfree.

Since the definition of a HGT-consistent labelling of a beadless phylogenetic
network $N$ does not rely on the assumption that $N$ has no beads, we extend
it to our type of phylogenetic network by dropping the “beadless” requirement
and qualifying Property (P3) by excluding reticulation vertices that are
contained in beads. In combination, Property (P2) and the thus adjusted
Property (P3) imply that there cannot have existed an ancestral species $v$
such that $v$ is involved in a polyploidization event and, at a later point in
time, one of its parents, $p$ say, hybridizes with the unique child $u$ of
$v$. Put differently, we cannot simultaneously have all three arcs $(v,u)$,
$(p,v)$, and $(p,u)$ and $v$ is a reticulation vertex.

In view of the aforementioned combined effect of Properties (P2) and (P3), we
also say that a phylogenetic network $N$ admits a weak HGT-consistent
labelling $t$ if $t$ is a map from the vertex set of $N$ to the set of non-
negative real numbers such that Properties (P1) and (P2) hold and Property
(P3) is weakened to

  1. (P3’)

there exists at most one reticulation vertex $v$ with distinct parents $u_{1}$
and $u_{2}$ with $u_{2}$ below $u_{1}$ such that $v$ does not satisfy Property
(P3) i. e. $t(u_{i})\not=t(v)$, for all $i=1,2$.

As a first observation, note that a HGT-consistent labelling of a phylogenetic
network is also a weak HGT-consistent labelling for that network.

To be able to state Theorem 5.1 which is concerned with clarifying the
structure of ploidy profiles that admit a HGT-consistent labelling or a weak
HGT-consistent labelling, we require the concept of a binary representation of
a positive integer $m$. This representation essentially records for the
representation of $m$ as a sum $\sum_{i=0}^{l}2^{q}$ of “powers of two” the
vector of exponents. More formally, we define the binary representation of a
positive integer $m=\sum_{j=1}^{k}2^{i_{j}}$ to be the vector
$(i_{1},\ldots,i_{k})$, $k\geq 1$, with $i_{j-1}>i_{j}$, for all $2\leq j\leq
k$, and $i_{k}\geq 0$. Note that although related, the binary representation
of $m$ is not the bit-wise representation of $m$. For example, for
$m=77=2^{6}+2^{3}+2^{2}+2^{0}$ the binary representation is $(6,3,2,0)$
whereas the bit-wise representation is $(1,0,0,1,1,0,1)$.

We say that a strictly simple ploidy profile $\vec{m}=(m_{1})$ is arc-rich if
the dimension of the binary representation of $m_{1}$ is at least two.
Furthermore, we call a ploidy profile $\vec{m}$ practical if either $\vec{m}$
is simple but not strictly simple or $\vec{m}=(m_{1})$ and $m_{1}$ is of the
form $m_{1}=2^{l}$, some $l\geq 1$. For example, the ploidy profile
$\vec{m}=(77)$ is arc-rich but not practical since the binary representation
of $77$ is the vector $(6,3,2,0)$.

######  Theorem 5.1.

Suppose $\vec{m}$ is a ploidy profile. If the terminal element $\vec{m_{t}}$
of the simplification sequence for $\vec{m}$ is practical then there exists a
core network for $\vec{m}$ that admits a HGT-consistent labelling. Otherwise,
$\vec{m_{t}}$ is arc-rich and there exists a core network for $\vec{m}$ that
admits a weak HGT-consistent labelling.

###### Proof.

For ease of readability, we split the proof into three sections, as indicated
below. We start with introducing a further concept. Suppose $T$ is a
phylogenetic tree on $X=\\{x_{1},\ldots,x_{n}\\}$, some $n\geq 2$. Then we
call $T$ a caterpillar tree (on $X$) if the elements of $X$ can be relabelled
in such a way that $T$ has a single cherry and that cherry is
$\\{x_{n-1},x_{n}\\}$. If $n\geq 3$ then $x_{1}$ is a leaf that is a child of
the root $\rho$ of $T$, and every vertex on the path from $\rho$ to the shared
parent $f$ of $x_{n}$ and $x_{n-1}$ other than $\rho$ and $f$ has a child that
is a leaf. For ease of presentation, we assume that the other child of the
parent $f^{\prime}$ of $f$ is $x_{n-2}$, the other child of the parent of
$f^{\prime}$ is $x_{n-3}$ and so on.

For the remainder of the proof, assume that $\vec{m}$ is a simple ploidy
profile (see Figure 4 for an illustration of our constructions for the ploidy
profile $\vec{m}=(77,1,1,1)$ on $X=\\{x_{1},\ldots,x_{4}\\}$). Since a core
network for $\vec{m}$ realizes the terminal element
$\vec{m_{t}}=(m_{1},\ldots,m_{n})$ of the simplification sequence for
$\vec{m}$ and $\vec{m_{t}}$ is simple, we need to consider the cases that
$\vec{m_{t}}$ is strictly simple and that $\vec{m_{t}}$ is not strictly
simple. Let $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ denote the set that indexes
$\vec{m_{t}}$. Recall that, by convention, $x_{i}$ indexes $m_{i}$, for all
$1\leq i\leq n$.

Construction of the core network $\mathcal{B}(\vec{m})$: Assume first that
$\vec{m_{t}}$ is a strictly simple ploidy profile. Then $\vec{m_{t}}=(m_{1})$
and $X=\\{x_{1}\\}$. Let $\vec{i}=(i_{1},\ldots,i_{k})$, some $k\geq 1$,
denote the binary representation of $m_{1}$. Note that $i_{1}\geq 1$ because
$m_{1}\geq 2$. Then we first construct a beaded tree $B(i_{1})$ that realizes
the strictly simple ploidy profile $(i_{1})$ by taking $i_{1}$ beads
$B_{1},B_{2},\ldots B_{i_{1}}$ and, provided $i_{1}\geq 2$, adding for all
$1\leq i\leq i_{1}-1$ an arc from the reticulation vertex $h_{i}$ of $B_{i}$
to the tree vertex of $B_{i+1}$. To the resulting graph we then add the vertex
$x_{1}$ and an arc $(h_{i_{1}},x_{1})$ to obtain $B(i_{1})$. If $m_{1}=2^{l}$,
some positive integer $l$, then we define $\mathcal{B}(\vec{m})$ to be
$B(i_{1})$.

So assume that there exists no positive integer $l$ such that $m_{1}=2^{l}$.
Then $k\geq 2$. Let $B(i_{1},i_{k})$ denote the phylogenetic network obtained
from $B(i_{1})$ by subdividing one of the two outgoing arcs of the root $\rho$
of $B(i_{1})$ by a subdivision vertex $s_{k}$, the outgoing arc of the
reticulation vertex in $B(i_{1})$ that has precisely $i_{k}$ reticulation
vertices strictly below it by a vertex $s_{k}^{\prime}$ and adding the arc
$a_{k}=(s_{k},s_{k}^{\prime})$. If $k=2$, then $\mathcal{B}(\vec{m})$ is
$B(i_{1},i_{2})$.

Finally, assume that $k\geq 3$. Then we first construct the graph
$B(i_{1},i_{k})$. Next, we subdivide the arc $a_{k}$ by $k-2$ vertices
$s_{2},\ldots,s_{k-1}$ such that $(s_{k},s_{2})$ is an arc and $s_{j}$ is the
parent of $s_{j+1}$ for all $2\leq j\leq k-2$. For all $2\leq j\leq k-1$, we
next subdivide the outgoing arc of the reticulation vertex of $B(i_{1},i_{k})$
that has precisely $i_{j}$ reticulation vertices of $B(i_{1})$ strictly below
it by a vertex $s_{j}^{\prime}$. Finally, we add for all such $j$ the arc
$a_{j}=(s_{j},s_{j}^{\prime})$ and denote the resulting graph by
$\mathcal{B}(\vec{m})$ in this case. By construction, $\mathcal{B}(\vec{m})$
is a phylogenetic network on $x_{1}$ that realizes $\vec{m_{t}}$ in either of
these cases for $k$.

So assume that $\vec{m_{t}}$ is not strictly simple. Then $m_{j}=1$, for all
$2\leq j\leq n$. Using the same notation as before, we first construct the
network $\mathcal{B}(\vec{m^{\prime}})$ for the ploidy profile
$\vec{m^{\prime}}=(m_{1})$. If $k=1$ then there exists some positive integer
$l$ such that $m_{1}=2^{l}$. Hence, $\mathcal{B}(\vec{m})$ is $B(i_{1})$ and
we subdivide one of the outgoing arcs of the root of $B(i_{1})$ by a vertex
$w$. So assume that $k\geq 2$. If $k=2$ then $\mathcal{B}(\vec{m^{\prime}})$
is $B(i_{1},i_{2})$ and we subdivide the arc $a_{2}$ of
$\mathcal{B}(\vec{m^{\prime}})$ by a vertex $w$. So assume $k\geq 3$. Then we
subdivide the arc $a=(s_{k-1},s_{k}^{\prime})$ of
$\mathcal{B}(\vec{m^{\prime}})$ by a vertex $w$. In either of these cases for
$k$ we then attach the caterpillar tree $T$ on $\\{x_{2},\ldots,x_{n}\\}$ to
$\mathcal{B}(\vec{m^{\prime}})$ via an arc from $w$ to the root of $T$ in case
$n\geq 3$. If $n=2$ then we attach the vertex $x_{n}$ via the pendant arc
$(w,x_{n})$. By construction, the resulting graph is a phylogenetic network
that realizes $\vec{m_{t}}$, and it is the network $\mathcal{B}(\vec{m})$ in
this final case for $\vec{m_{t}}$.

Construction of a HGT-consistent labelling for $\mathcal{B}(\vec{m})$ in case
$\vec{m_{t}}$ is practical: Assume first that $\vec{m_{t}}$ is strictly
simple. Then $m_{1}=2^{i_{1}}$ and $\mathcal{B}(\vec{m})$ is $B(i_{1})$.
Hence, there exists a directed path
$P:v_{0}=\rho,v_{1},v_{2},\ldots,v_{q}=x_{1}$ from the root $\rho$ of
$\mathcal{B}(\vec{m})$ to $x_{1}$ once one arc has been removed from each bead
of $\mathcal{B}(\vec{m})$. Note that $P$ contains vertices with indegree and
outdegree one and that $V(P)$ is the vertex set of $\mathcal{B}(\vec{m})$.
Consider the map $t:V(P)\to\mathbb{R}_{\geq 0}$ defined by putting
$t(v_{0})=0$ and $t(v_{j+1})=t(v_{j})+1$, for all other $0\leq j\leq q-1$. By
construction, it follows that $t$ is a HGT-consistent labelling for
$\mathcal{B}(\vec{m})$ in this case.

So assume that $\vec{m_{t}}$ is not strictly simple. Then $\vec{m_{t}}$ must
be simple because it is the terminal element of the simplification sequence
for $\vec{m}$. Let $P:v_{0}=\rho,v_{1},v_{2},\ldots,v_{q}=x_{1}$ denote the
directed path in $\mathcal{B}(\vec{m})$ from $\rho$ to $x_{1}$ obtained by
removing (i) the caterpillar tree on $\\{x_{2},\ldots,x_{n}\\}$ and the
incoming arc of its root in case $n\geq 3$ and $x_{n}$ and its pendant arc if
$n=2$, (ii) for all $2\leq j\leq k$, the vertices $s_{j}$ and their incident
arcs, and (iii) one of the two arcs in every bead. Let
$t_{P}:V(P)\to\mathbb{R}_{\geq 0}$ be defined as the map $t$ in the previous
case.

Consider the map $t:V(\mathcal{B}(\vec{m}))\to\mathbb{R}_{\geq 0}$ defined by
putting $t(v)=t_{P}(v)$ for all vertices $v$ of $\mathcal{B}(\vec{m})$ that
are also vertices on $P$. So let $v$ be a vertex in $\mathcal{B}(\vec{m})$
that does not lie on $P$. If $v=s_{k}$ then put $t(v)=t(h_{1})$ and if $v=w$
then put $t(v)=t(s^{\prime}_{k})$. For all $2\leq j\leq k-1$, put
$t(s_{j})=t(s^{\prime}_{j})$. Note that this does not violate Properties
(P1)-(P3) since, for all $2\leq j\leq k-1$, we have
$t(s_{j}^{\prime})<t(s_{j+1}^{\prime})$ and
$t(s_{k})<t(h_{1})<t(s_{2}^{\prime})=t(s_{2})$. If $n\geq 3$ then, for all
$1\leq j\leq n-1$, let $w_{j}$ denote that parent of the leaf $x_{j+1}$ of
$T$. Put $t(w_{1})=t(w)+1$ and, for all $1\leq j\leq n-2$, put
$t(w_{j+1})=t(w_{j})+1$. Finally, choose a value $\chi>t(w_{n-1})$ and put
$t(x_{j})=\chi$, for all $2\leq j\leq n$. By construction, $t$ respects
Properties (P1)-(P3), and so $t$ is a HGT-consistent labelling for
$\mathcal{B}(\vec{m})$. If $n=2$ then we proceed in a similar manner in that
we put $t(x_{n})=t(w)+1$.

Construction of a weak HGT-consistent labelling for $\mathcal{B}(\vec{m})$ in
case $\vec{m_{t}}$ is not practical: If $\vec{m_{t}}$ is not practical it must
be arc-rich as $\vec{m_{t}}$ is the terminal element of the simplification
sequence of $\vec{m}$. It suffices to note that a weak HGT-consistent
labelling can be constructed as in the case of a HGT-consistent labelling
noting that the only reticulation vertex of $\mathcal{B}(\vec{m})$ that
violates Property (P3) is $s_{k}^{\prime}$. Thus, $t$ satisfies Property (P3’)
and so $\mathcal{B}(\vec{m})$ admits a weak HGT-consistent labelling. $\Box$ ∎

As mentioned in the proof of Theorem 5.1, we next illustrate the construction
of $\mathcal{B}(\vec{m})$ for the ploidy profile $\vec{m}=(77,1,1,1)$ on
$X=\\{x_{1},x_{2},x_{3},x_{4}\\}$. Then the vector $\vec{i}=(6,3,2,0)$ is a
binary representation for $77$ and the phylogenetic network depicted in Figure
4(i) is $\mathcal{B}(\vec{m^{\prime}})$ where $\vec{m^{\prime}}=(77)$.
Clearly, the phylogenetic network $\mathcal{B}(\vec{m})$ depicted in Figure
4(ii) obtained from $\mathcal{B}(\vec{m^{\prime}})$ by adding the leaves
$x_{2}$, $x_{3}$, and $x_{4}$ as indicated realizes $\vec{m}$ and admits a
HGT-consistent labelling. Since the actual time stamp values are of no
interest to our discussion, we indicate arcs for which both end vertices have
the same time stamp under a HGT-consistent labelling in terms of horizontal
arcs.

Figure 4. (i) The core network ${\mathcal{B}}(\vec{m^{\prime}})$ for the
strictly simple ploidy profile $\vec{m^{\prime}}=(77)$ on $X=\\{x_{1}\\}$.
(ii) The core network $\mathcal{B}(\vec{m})$ for the simple ploidy profile
$\vec{m}=(77,1,1,1)$ on $\\{x_{1},x_{2},x_{3},x_{4}\\}$ obtained from
$\mathcal{B}(\vec{m^{\prime}})$. Alternative core networks for $\vec{m}$ can
be obtained from $\mathcal{B}(\vec{m^{\prime}})$ by subdividing non-bold arcs
and attaching the remaining elements of $X$ as phylogenetic trees on subsets
of $X$ or individually (ensuring that the arc $(s_{3},s_{4}^{\prime})$ is
subdivided at a least once as otherwise the resulting phylogenetic network
does not admit a HGT-consistent labelling because Property (P3) is violated).

As indicated in Figure 5, alternative choices of a core network for a ploidy
profile $\vec{m}$ are conceivable in the sense that it might not be obtained
by starting with a binary representation of the first component of $\vec{m}$.
Furthermore and perhaps not surprisingly, a core network $N$ for $\vec{m}$
generally admits more than one HGT-consistent labelling in the sense that an
alternative HGT-consistent labelling for $N$ might assign for a reticulation
vertex $v$ the same time stamp as for $v$ to a different parent of $v$.

Figure 5. (i) The realization $\mathcal{B}(\vec{m})$ of the practical ploidy
profile $\vec{m}=(12,1,1)$ on $X=\\{x_{1},x_{2},x_{3}\\}$. (ii) A core network
for $\vec{m}$ that is not of the form $\mathcal{B}(\vec{m})$.

The fact that the simplification sequence of a ploidy profile $\vec{m}$ is
obtained by taking differences of the first two consecutive components of
$\vec{m}$ implies that, in general, properties of ploidy profiles do not get
inherited by ploidy profiles obtained from $\vec{m}$. For certain types of
ploidy profiles this is however not the case as the following consequence of
Theorem 5.1 shows.

######  Corollary 5.2.

Suppose that $\vec{m}$ is a ploidy profile. Then the following holds.

  1. (i)

If $\vec{m}$ is of the form $(n,n-1,n-2,\ldots,1)$, $n\geq 3$, then, for any
ploidy profile obtained from $\vec{m}$ by removing at most one of its
components, there exists a core network that admits a HGT-consistent
labelling.

  2. (ii)

If $\vec{m}=(m_{1},\ldots,m_{n})$ then there exists a core network for
$(m_{1},\ldots,m_{n},1)$ that admits a HGT-consistent labelling.

  3. (iii)

If $\vec{m}=(m_{1},\ldots,m_{n})$ has a core network that admits a HGT-
consistent labelling then the ploidy profile
$(2^{i}m_{1},\ldots,2^{i}m_{n},2^{i-1},2^{i-2}\ldots,2^{0})$, $i\geq 1$, has a
realization that also admits such a labelling.

###### Proof.

(i) Let $\vec{m^{\prime}}$ denote a ploidy profile obtained from $\vec{m}$ as
described in the statement of the corollary. Then the difference between any
two consecutive component values in $\vec{m}$ is $1$ if no component is
removed from $\vec{m}$ (i. e. $\vec{m}=\vec{m^{\prime}}$) or if a component is
removed from $\vec{m}$ to obtain $\vec{m^{\prime}}$ whose value is not 2. In
either of these two cases, it follows that the terminal element
$\vec{m^{\prime}_{t}}$ of the simplification sequence for $\vec{m^{\prime}}$
is of the form $(2,1,\ldots,1)$. If the component with value 2 is removed to
obtain $\vec{m^{\prime}}$ from $\vec{m}$ then the terminal element
$\vec{m^{\prime}_{t}}$ of $\sigma(\vec{m^{\prime}})$ is of the form
$(3,1,\ldots,1)$ as that ploidy profile is simple. In either of these cases,
$\vec{m^{\prime}_{t}}$ is practical. Applying Theorem 5.1 implies the result.

(ii) To see the assertion, it suffices to note that the terminal element of
the simplification sequence for $\vec{m^{\prime}}=(m_{1},\ldots,m_{n},1)$ is
practical because it is of the form $(m,1,\ldots,1)$, some $m\geq 2$.

(iii) Put
$\vec{m^{\prime}}=(2^{i}m_{1},\ldots,2^{i}m_{n},2^{i-1},2^{i-2}\ldots,2^{0})$.
Let $\mathcal{B}(\vec{m})$ initialize the construction of $N=N(\vec{m})$.
Since, by assumption, $\mathcal{B}(\vec{m})$ admits a HGT-consistent
labelling, it follows by construction that $N$ also admits such a labelling.
Let $t:V(N)\to\mathbb{R}_{\geq 0}$ denote a HGT-consistent labelling for $N$.

Next, consider the ploidy profile
$\vec{m^{\prime\prime}}=(2^{i-1},2^{i-2}\ldots,2^{0})$ on $X$ where $x_{n+j}$
indexes $2^{i-j}$, for all $1\leq j\leq i$. Then construct the core network
$\mathcal{B}(\vec{m^{\prime\prime}})$ for $\vec{m^{\prime\prime}}$. Since
$\vec{m^{\prime\prime}_{t}}=(2,1)$ and therefore is not strictly simple
$\mathcal{B}(\vec{m^{\prime\prime}})$ admits a HGT-consistent labelling.
Initializing the construction of $N^{\prime\prime}=N(\vec{m^{\prime\prime}})$
with $\mathcal{B}(\vec{m^{\prime\prime}})$ implies that $N^{\prime\prime}$
also admits a HGT-consistent labelling
$t^{\prime\prime}:V(N^{\prime\prime})\to\mathbb{R}_{\geq 0}$.

Next, construct a realization $N^{\prime}$ for $\vec{m^{\prime}}$ from $N$ and
$N^{\prime\prime}$ by subdividing the incoming arc of $x_{n+1}$ by two new
vertices $s$ and $s^{\prime}$ such that $s^{\prime}$ is below $s$. Next, add a
further vertex $s^{\prime\prime}$ and the arcs $(s,s^{\prime\prime})$,
$(s^{\prime},s^{\prime\prime})$, and $(s^{\prime\prime},q)$ where $q$ is the
root of $N$ to obtain $N^{\prime}$. To obtain a HGT-consistent labelling
$t^{\prime}:V(N^{\prime})\to\mathbb{R}_{\geq 0}$ for $N^{\prime}$ put
$t^{\prime}(v)=t^{\prime\prime}(v)$ for all vertices $v$ of $N^{\prime}$ that
are also vertices in $N^{\prime\prime}$. Next, choose a value
$t^{\prime\prime}(p)<\omega<t^{\prime\prime}(x_{n+1})$ where $p$ is the parent
of $x_{n+1}$ in $N^{\prime\prime}$ and put $t^{\prime}(s)=\omega$,
$t^{\prime}(s^{\prime})=t^{\prime}(s^{\prime\prime})=\omega+\epsilon$, some
$\epsilon>0$ sufficiently small, and $t^{\prime}(q)=t^{\prime}(s)+1$. Finally,
for all vertices $v$ in $N$ put $t^{\prime}(v)=t(v)+t^{\prime}(q)+1$. Since
$t^{\prime\prime}$ is a HGT-consistent labelling for $N^{\prime\prime}$ and
$t$ is such a labelling for $N$ it follows by construction that $t^{\prime}$
is a HGT-consistent labelling for $N^{\prime}$. $\Box$

∎

To help illustrate Corollary 5.2(iii), consider the ploidy profile
$\vec{m^{\prime}}=(40,24,8,$ $4,2,1)=(2^{3}\times 5,2^{3}\times 3,2^{3}\times
1,2^{2},2^{1},2^{0})$ on $X=\\{x_{1},\ldots,x_{6}\\}$. Then $i=3$ and
$\vec{m}$ is the ploidy profile $(5,3,1)$ on $\\{x_{1},x_{2},x_{3}\\}$. Hence,
$\vec{m_{t}}=(2,1,1)$. By Theorem 5.1, $\mathcal{B}(\vec{m})$ admits a HGT-
consistent labelling because $\vec{m_{t}}$ is practical. Initializing the
construction of $N=N(\vec{m})$ with $\mathcal{B}(\vec{m})$ implies that $N$
also admits a HGT-consistent labelling. The part of the network $N^{\prime}$
pictured in Figure 6

Figure 6. The realization $N^{\prime}$ of the ploidy profile
$\vec{m^{\prime}}=(40,24,8,4,2,1)$ in terms of a phylogenetic network with
horizontal arcs.

that is labelled $N$ is that realization with a HGT-consistent labelling
indicated in terms of horizontal arcs. The part of $N^{\prime}$ labelled
$N^{\prime\prime}=N(\vec{m^{\prime\prime}})$ is a realization of the ploidy
profile $\vec{m^{\prime\prime}}=(4,2,1)$ on $\\{x_{4},x_{5},x_{6}\\}$ once the
three incident arcs of $s^{\prime\prime}$ are ignored and $s^{\prime\prime}$
and the resulting vertices with indegree and outdegree one are suppressed. By
construction, $N^{\prime}$ is a realization of $\vec{m^{\prime}}$ that admits
a HGT-consistent labelling (again indicated in terms of horizontal arcs).

We conclude this section with remarking that Corollary 5.2(ii) is of
particular interest from a “ghost species” point of view in that the element
$x_{n+1}$ indexing the last component of $(m_{1},\ldots,m_{n},1)$ could
represent a taxon with ploidy level one that has not been sampled yet (see e.
g. [30] for the case of banana).

##  6\. When is $N(\vec{m})$ a tree with additional horizontal arcs?

As was established in [35, Section 2.1], beadless phylogenetic networks that
admit a HGT-consistent labelling are precisely the ones that admit a so called
complete cherry reduction sequence. These types of sequences essentially
record how to transform a (beadless) phylogenetic network into a single vertex
by applying only operations on pairs of leaves, provided this is possible. In
view of [35, Theorem 1] and [7], their attraction lies in the fact that they
can be used to quickly check if a given (beadless) phylogenetic network can be
represented with horizontal arcs without having to find a HGT-consistent
labelling for it first. Therefore it is of interest to see if an analogous
result holds for our types of phylogenetic networks. To be able to shed light
into this question, we first need to extend the concept of a cherry reduction
sequence to our types of phylogenetic networks. For this we require further
terminology.

Suppose that $N$ is a phylogenetic network on $X$. Assume first that $X$ has
at least two elements and that $a$ and $b$ are distinct elements in $X$. If
$\\{a,b\\}$ is a cherry of $N$ then we refer to the operation of deleting $b$
and its incoming arc and suppressing the resulting vertex of indegree and
outdegree one as reducing the cherry $\\{a,b\\}$ by $b$. We denote this
operation by $reduce(a,b)$. Note that if the joint parent of $a$ and of $b$ is
the root $\rho$ of $N$ and $N$ therefore has leaf set $\\{a,b\\}$, then this
operation also includes post-processing the resulting graph by collapsing the
unique arc from $\rho$ to $a$ to obtain the single vertex $a$. If $a$ and $b$
form a reticulated cherry of $N$ such that $b$ is the reticulation leaf then
we refer to the operation of deleting the reticulation arc and suppressing the
resulting vertices of indegree and outdegree one as cutting the cherry
$\\{a,b\\}$. We denote this operation by $cut(a,b)$. For example, deleting the
thin arc incident with the parent of $x_{1}$ in the network $N_{0}$ pictured
in Figure 2 is the cutting operation $cut(x_{2},x_{1})$. Deleting the leaf
$x_{1}$ in the network $N_{1}$ pictured in that figure is the reducing
operation $reduce(x_{2},x_{1})$.

Finally assume that $a$ is the sole element of $X$. Then we refer to the set
$\\{a\\}$ as a type-1 degenerate cherry if the parent of $a$ is the
reticulation vertex in a bead $B$. In this case we call the operation of
removing one of the two arcs of $B$, suppressing resulting vertices with
indegree and outdegree one, and also collapsing the unique outgoing arc of the
tree vertex of $B$ if that has rendered it a vertex of outdegree one as
simplification of $a$. We denote this operation by $simp(a)$. Furthermore, we
refer to the set $\\{a\\}$ as a type-2 degenerate cherry if $a$ has a parent
$p$ that is a reticulation vertex and either (i) precisely one of the parents
$q_{1}$ and $q_{2}$ of $p$ is the reticulation vertex of a bead or (ii) there
exists a further vertex $q$ such that $N$ also contains (a) the three arcs
$(q,q_{1})$, $(q,q_{2})$, and $(q_{1},q_{2})$, or (b) the arc $(q_{1},q)$ and
a pair of arcs from $q$ to $q_{2}$. Assuming that Case (ii) holds then, we
refer to the operation of deleting the arc $(q_{1},p)$ (Case (a)) and deleting
one of the arcs from $q$ to $q_{2}$ (Case (b)) and in each case suppressing
the two resulting vertices of indegree and outdegree 1 as trimming of $a$.

We denote this operation as $trim(a)$. For example for the network pictured in
Figure 4(i), the trimming operation $trim(x_{1})$ consists of deleting the arc
$(s_{3},s_{4}^{\prime})$ and suppressing the vertices $s_{4}^{\prime}$ and
$s_{3}$. Removing one of the two arcs in the bead in the network depicted in
Figure 5(i) that contains the parent of $x_{1}$ is the simplification
operation $simp(x_{1})$.

It is easily seen that the operations of reducing a cherry and cutting a
reticulated cherry both result in a phylogenetic network where, for technical
reasons, we refer in this context to an isolated vertex $a$ also as a
phylogenetic network on $\\{a\\}$. Collectively, these two operations are
usually referred to as cherry reduction operations. Since our type of
phylogenetic networks may contain beads, we extend this convention by
collectively referring to a cherry reduction operation, a simplification of a
type-1 degenerate cherry, and the trimming of a type-2 degenerate cherry as a
cherry modification operation.

Following [2], we call a sequence $\chi$ of elements in $X$ a complete cherry
reduction sequence for a beadless phylogenetic network $N$ on $X$ if either
(i) $\chi$ only contains $N$ if $N$ is a single vertex or (ii) $\chi$ is the
sequence $N=N_{0},N_{1},N_{2},\ldots,N_{k},N_{k+1}$ of phylogenetic networks
$N_{i}$, $0\leq i\leq k+1$, such that, for all $1\leq i\leq k+1$, the network
$N_{i}$ is obtained from $N_{i-1}$ by a (single) cherry reduction operation
and $N_{k+1}$ is a single vertex. A (beadless) phylogenetic network that
admits a complete cherry reduction sequence is also called an orchard. With
this in mind, we say that a phylogenetic network $N$ of our type has a
complete cherry modification sequence if $N$ has an augmented complete cherry
reduction sequence in the sense that, in addition to cherry reduction
operations, the only other permitted operation is simplification of a type-1
degenerate cherry. For consistency reasons, we call a phylogenetic network
that admits a complete cherry modification sequence also an orchard in this
case.

Similarly, we call a sequence of cherry modifications operations a complete
weak cherry modification sequence for $N$, if $N$ has an augmented complete
cherry modification sequence in the sense that, in addition to cherry
reduction operations and the simplification of type-1 degenerate cherries, the
trimming of a type-2 degenerate cherry is also allowed. In that case, we also
call $N$ a weak orchard.

For example and bearing in mind that the leaf labels are affected by the
operations that govern the generation of the simplification sequence for
$\vec{m}$, the sequence of phylogenetic networks depicted in Figure 2 read
from right to left combined with the cherry modification sequence of the core
network $\mathcal{B}(\vec{m})$ of $\vec{m}=(7,6,6,5)$ pictured in Figure 7

Figure 7. A complete cherry modification sequence for the core network
$\mathcal{B}(\vec{m})$ of $\vec{m}=(7,6,6,5)$. The applied cherry
modifications operations are indicated above the arrows between the networks.

is a complete cherry modification sequence for the realization $N(\vec{m})$ of
$\vec{m}$ depicted in Figure 2. On the other hand, the sequence presented in
Figure 8

Figure 8. A weak cherry modification sequence for the realization
$N(\vec{m})$, depicted on the left, of the ploidy profile $\vec{m}=(6,3)$ on
$\\{x_{1},x_{2}\\}$.

is a weak cherry modification sequence for $N(\vec{m})$ where $\vec{m}$ is the
ploidy profile $(6,3)$ on $\\{x_{1},x_{2}\\}$.

Note that neither a complete cherry reduction sequence nor a complete weak
cherry modification sequence might exist for a realization of a ploidy profile
and also that, in case it does exist, such a realization might have more than
one.

The fact that an orchard and also a weak orchard induces a ploidy profile by
taking numbers of directed paths from the root of the network to each of its
leaves lies at the heart of our extension of these concepts to ploidy
profiles. More precisely, if $\vec{m}$ is a ploidy profile that is realized by
a phylogenetic network $N$ and $N$ is an orchard then we call $\vec{m}$ an
orchard (with respect to $N$). If $N$ is a weak orchard then we call $\vec{m}$
a weak orchard (with respect to $N$). To simplify terminology, we refer to
$\vec{m}$ simply as an orchard or a weak orchard if the knowledge of $N$ is of
no relevance to the discussion. For example and each time initializing the
construction of the realization $N(\vec{m})$ by $\mathcal{B}(\vec{m})$, the
ploidy profile $\vec{m}=(7,6,6,5)$ is an orchard with respect to $N(\vec{m})$,
and the ploidy profile $\vec{m}=(6,3)$ is a weak orchard with respect to its
realization $N(\vec{m})$. Thus, $\vec{m}=(7,6,6,5)$ is an orchard and
$\vec{m}=(6,3)$ is a weak orchard. Furthermore, an exhaustive search for the
ploidy profile $\vec{m}=(3)$ shows that there exist ploidy profiles that are a
weak orchard but not an orchard.

The next result formalizes a link suggested by these two examples between
complete cherry modification sequences and simplification sequences. At its
heart lies a characterization of (beadless) orchards in terms of HGT-
consistent labellings [35, Theorem 1].

######  Theorem 6.1.

Suppose $\vec{m}$ is a ploidy profile on $X$. If $\vec{m}$ is practical then
every ploidy profile in the simplification sequence $\sigma(\vec{m})$ of
$\vec{m}$ is orchard. Furthermore, the traceback through $\sigma(\vec{m})$
combined with a cherry modification sequence for $\mathcal{B}(\vec{m})$ gives
rise to a complete cherry modification sequence for $N(\vec{m})$ provided the
construction of $N(\vec{m})$ is initialized with $\mathcal{B}(\vec{m})$.

###### Proof.

Since $\vec{m}$ is practical, Theorem 5.1 implies that $\mathcal{B}(\vec{m})$
admits a HGT-consistent labelling. Combined with a canonical extension of [35,
Theorem 1] to our types of phylogenetic networks, it follows that there exists
a complete cherry modification sequence for $\mathcal{B}(\vec{m})$. To see
that $N(\vec{m})$ has a complete cherry modification sequence it therefore
suffices to show that at each step in the traceback of $\sigma(\vec{m})$ only
a cherry or a reticulate cherry is introduced.

Assume for the remainder that the construction of $N(\vec{m})$ is initialized
with $\mathcal{B}(\vec{m})$. Then $N(\vec{m_{t}})$ has a complete cherry
modification sequence by assumption on $\mathcal{B}(\vec{m})$ as
$N(\vec{m_{t}})$ is $\mathcal{B}(\vec{m})$. Using the same notation as in the
construction of $N(\vec{m})$ outlined in Section 3 either $\alpha=0$, or
$\alpha>m_{2}^{\prime}$, or $\alpha\leq m_{2}^{\prime}$. Let
$N^{\prime\prime}$ denote a realization for $\vec{m^{\prime\prime}}$
constructed from $\mathcal{B}(\vec{m})$ as described in the construction of
$N(\vec{m})$.

Employing the same indexing scheme as in the construction of $N(\vec{m})$, it
follows that to realize $\vec{m^{\prime}}$, the leaf indexing the first
component of $\vec{m^{\prime\prime}}$ is replaced by the cherry
$\\{x_{1}^{\prime},x_{2}^{\prime}\\}$ if $\alpha=0$. In the two remaining
cases a single reticulate cherry on $\\{x_{1}^{\prime},x_{2}^{\prime}\\}$ with
reticulate leaf $x_{1}^{\prime}$ is generated. Thus, the generated realization
of $\vec{m^{\prime}}$, i. e. $N(\vec{m^{\prime}})$, is orchard. It follows
that every ploidy profile in $\sigma(\vec{m})$ is orchard. The remainder of
the theorem is an immediate consequence. $\Box$

∎

Since, as mentioned in the proof of Theorem 6.1, the reversal of the
operations to construct the network $N(\vec{m})$ from the core network
$\mathcal{B}(\vec{m})$ corresponds to applying a single cherry reduction
operation in each step of the traceback through $\sigma(\vec{m})$, the
companion result for ploidy profiles where $\mathcal{B}(\vec{m})$ admits a
weak HGT-consistent labelling also holds. Put differently, the result stated
in Theorem 6.1 with the text “If $\vec{m}$ is practical” omitted, the word
“orchard”, replaced by “weak orchard” and the text “concatenated with a cherry
modification sequence for $\mathcal{B}(\vec{m})$ results in a complete cherry
modification sequence for $N(\vec{m})$” replaced by “concatenated with a weak
cherry modification sequence for $\mathcal{B}(\vec{m})$ results in a complete
weak cherry modification sequence for $N(\vec{m})$” also holds.

Intriguingly, the core network $\mathcal{B}(\vec{m})$ for $\vec{m}=(77,1,1,1)$
depicted in Figure 4(i) gives rise to a phylogenetic tree on
$\\{x_{1},\ldots,x_{4}\\}$ by deleting all horizontal arcs and removing one
arc from each bead (each time suppressing the resulting vertices of indegree
and outdegree one and the root in case this has rendered it a vertex with
outdegree one). Beadless phylogenetic networks that enjoy this property are
called tree-based [8] and have recently attracted a considerable amount of
attention in the phylogenetic networks community (see, for example, [33,
Chapter 10.4.2]) since they can be thought of as phylogenetic trees to which
arcs have been added. More precisely, a phylogenetic network $N$ is called
tree-based if there exists a phylogenetic tree $T$ such that when first adding
an incoming arc to the root of $T$ to obtain a tree $T^{\prime}$ and then
subdividing some of the arcs of $T^{\prime}$ and adding arcs between the
generated subdivision vertices (ensuring that no directed cycle is created and
the overall degree sum of the subdivision vertices is 3) the resulting
directed graph is $N$. In that case, $T$ is called a base tree for $N$.

As it turns out, the above observation for $\vec{m}=(77,1,1,1)$ and
$\mathcal{B}(\vec{m})$ is not a coincidence as the following more general
result holds.

######  Theorem 6.2.

Suppose $\vec{m}$ is a ploidy profile on $X$. If $\vec{m}$ is practical then
the network $N(\vec{m})$ generated from $\mathcal{B}(\vec{m})$ is tree-based.

###### Proof.

This is an immediate consequence of Theorem 6.1 and the fact that the added
horizontal arcs of $N(\vec{m})$ correspond to reticulation arcs in reticulate
cherries. $\Box$

∎

Interestingly, the corresponding result for arc-rich ploidy profiles does not
hold as the core network depicted in Figure 4(i) shows.

##  7\. A Viola dataset

In this section, we apply our findings to a simplified version of a dataset
studied in [24] to better understand the evolutionary past of plants in the
genus Viola. The findings of the authors of that paper include a most
parsimonious PADRE reconstruction of allopolyploid relationships within Viola,
showing nine polyploidisation events (two of which involve more than two
ancestral species) to explain the dataset’s ploidy levels which range from
$2\times$ to $18\times$ [24, Figure 4]. To help ensure readability, we present
a simplified version of that network in Figure 9(i). To obtain it, we focused
on (i) retaining the polyploidization events suggested by [24, Figure 4] and
the directed paths in the network which involve them, and (ii) representing
subtrees in terms of single leaves. More precisely, we removed the taxa:
V.diffusa, V.papuana, V.selkirkii, V.somchetica, V.tuberifa, V.renifola,
V.principis, V.vaginata, V.epipsila, V.pallens, V.lanceolata, V.primulifolia,
V.jalapaënsis, V.occidentalis, V.pedata, V.clauseniana, V.sagittata,
V.pubescens, V.lobata. Furthermore, we summarized the taxa V.capillaris and
V.rubella into the label rubellium as they formed a cherry and the taxa
V.laricicola, V.striata, V.stagnina, V.uliginosa, V.mirabilis, V.chelmea,
V.collina, V.hirta into the label viola as they formed a subtree. Finally,
since the network in [24, Figure 4] contained two vertices with indegree
three, we have resolved them as indicated in Figure 9(i). More precisely, the
resolved vertices are the vertex labelled $10\times$ and its parent labelled
$8\times$ and also the vertex labelled $18\times$ and its parent labelled
$14\times$.

Figure 9. (i) A phylogenetic network on $X=\\{$rubellium, viola, V.verecunda,
V.blande, V.repens, V.933palustris, V.721palustris, V.macloskeyi,
V.langsdorff, V.tracheliffolia, V.grahamii, V.glabella$\\}$ adapted from [24].
To improve clarity we include the ploidy level of each reticulation vertex.
Apart from rubellium and viola which are denoted ru and vi, respectively,
leaves are labelled by the first two characters of their name (omitting “V.”).
(ii) The realization $N(\vec{m})$ of the ploidy profile $\vec{m}$ induced by
the network in (i). Contrary to the network in (i), $N(\vec{m})$ is orchard.
In each case, the graph obtained by removing the non-bold arcs is a base tree
for $N(\vec{m})$. For ease of readability, the labels of the non-leaf vertices
represent the number of directed paths from the root to that vertex in each of
(i) and (ii).

Although the network pictured in Figure 9(i) clearly represents the ploidy
profile $\vec{m}=(18,14,14,10,8,8,8,4,4,2)$ by taking the number of directed
paths from the root to each leaf, from a formal point of view, it is not a
realization of $\vec{m}$ since the ancestral species at the root is assumed to
be diploid. This shortcoming of our framework can however easily be rectified
by adding a bead via an incoming arc to the root of the network.

As was established in [11, Theorem 2], the minimum number of reticulation
vertices required by a phylogenetic network to realize $\vec{m}$ is 5. Since
the phylogenetic network $N(\vec{m})$ pictured in Figure 9(ii) realizes
$\vec{m}$ using five reticulation vertices it follows that it is optimal with
regards to this property. Furthermore since none of the five reticulation
vertices are contained in a bead, they all represent allopolyploidization
events. Finally, $N(\vec{m})$ admits a HGT-consistent labelling which implies
that $\vec{m}$ is orchard. In turn, this implies that a phylogenetic network
that realizes $\vec{m}$ can be obtained from a phylogenetic tree (in this case
without beads) by adding horizontal arcs. Given these attractive features it
could be of interest to better understand to what extent the network
$N(\vec{m})$ can be used to inform the construction of a multiple-labelled
tree such as the one underpinning the network in Figure 9(i). As mentioned
above already, constructing such a tree is not easy in general [10].

Using the insights from Section 4 to help assess how different the two
networks in Figure 9 are, assume that the chosen distance measure for
comparing two multiple-labelled trees is the SPR-distance. Then by first
applying split-operations to each of the two networks pictured in Figure 9
until a multiple-labelled tree is obtained and then transforming one of the
two obtained multiple-labelled trees into the other via a sequence
$\chi_{SPR}$ of multiple-labelled trees such that two consecutive multiple-
labelled trees in $\chi_{SPR}$ have SPR-distance 1 yields an upper bound of 26
on the $D_{\mathcal{P}(\vec{m})}$-distance between the two networks.

##  8\. Concluding remarks

In this paper, we have pushed back the current limits of the emerging field of
Polyploid Phylogenetics [29] by studying combinatorial properties of a ploidy
profile $\vec{m}$ on some set $X$. Denoting by $N(\vec{m})$ the phylogenetic
network obtained as a slightly modified version of the construction of a
phylogenetic network that appeared in [11], we show that $N(\vec{m})$ may be
viewed as a generator of ploidy profile space $\mathcal{P}(\vec{m})$ in the
sense that any other realization $N$ of $\vec{m}$ can be obtained from it by
going along the edges of a path from $N(\vec{m})$ to $N$ in
$\mathcal{P}(\vec{m})$ (Proposition 4.1). Furthermore, $N(\vec{m})$ may be
thought of as a phylogenetic tree with beads to which additional arcs have
been added (Theorem 6.2) and at most one of these additional arcs cannot be
drawn as a horizontal arc (Theorem 5.1). Furthermore, we establish a close
link between the concept of a cherry reduction sequence for $N(\vec{m})$ and
the simpification sequence for $\vec{m}$, a concept which underpins the
construction of $N(\vec{m})$ (Theorem 6.1). As an immediate consequence, we
also have that the ploidy profile space for the ploidy profiles described in
Corollary 5.2 can be generated from a phylogenetic tree with beads and only
horizontal arcs added. Finally, we illustrate our findings by means of a real
biological dataset.

Although our results are encouraging, numerous open questions remain. From a
more biological point of view, these include understanding how well the
$D_{\mathcal{P}(\vec{m})}$-distance captures similarity between different
realizations of a ploidy profile $\vec{m}$. In the context of this it should
be noted that the edit-distance type nature of the
$D_{\mathcal{P}(\vec{m})}$-distance implies that, in general, it might be
computationally difficult to compute it. This immediately begs the more
mathematical question of how to bound it.

Also, it might be useful to explore diameter bounds for the
$D_{\mathcal{P}(\vec{m})}$-distance and the effect the choice of distance
measure on multiple-labelled trees has. The same also holds when replacing the
sequence of split operations to obtain a multiple-labelled tree from a
phylogenetic network with the “unfold” operation for phylogenetic networks.
Essentially, this operation associates a multiple-labelled tree to a
phylogenetic network $N$ by recording for every leaf $x$ of $N$ all directed
paths from the root of $N$ to $x$ (see e. g. [12, 14] for details about this
operation). It may also be interesting to explore the relationship between the
simplification sequence and trinets [17]. For example, how are the classes of
phylogenetic networks that can be determined from trinets related to the class
of phylogenetic networks with complete cherry reduction sequences?

In a different direction, it might be of interest to see if the results and
approaches presented here can be extended to include further evolutionary
processes such as aneuploidy whereby only a subset of the chromosome set of a
genome (as opposed to the whole set of chromosomes) occurs multiple times.
This could potentially involve representing a polyploid species not in terms
of a ploidy level but in terms of a vector with each component representing
the number of times the chromosome indexing it is found. A ploidy profile
would in that case not be a vector of positive integers but a vector of
vectors, each of them indexed by a species. Although attractive at first
glance, this would require finding a new way of realizing a ploidy profile in
terms of a phylogenetic network.

From a more mathematical point of view, it might also be interesting to
investigate if a ploidy profile $\vec{m}$ whose simplification sequences
terminates in a practical ploidy profile can be characterized without having
to compute the simplification sequence of $\vec{m}$ first. This might require
a better understanding of the link between simplifications sequences and
ploidy profiles that are orchard. The availability of such a characterization
could potentially lead to a fast way to decide if a ploidy profile $\vec{m}$
can be realized by an orchard.

In the case of beadless phylogenetic networks, relationships between various
types of properties are known. For example every orchard is also tree-based
[35, Corollary 2] and also every tree-child network is orchard [4]. Tree-child
networks are defined as those (beadless) phylogenetic networks for which, for
every one of its vertices $v$, there exists a directed path $P$ to a leaf so
that no vertex on $P$ other than potentially $v$ is a reticulation vertex.
Extending this property canonically to our types of networks by allowing $P$
to contain reticulation vertices in beads results in a natural way to extend
the tree-child concept to our types of phylogenetic networks. More precisely,
we call a ploidy profile tree-child if it has a realization that is tree-child
when reticulation vertices in beads are ignored.

As is easy to see, if the construction of $N(\vec{m})$ is initialized with the
core network $\mathcal{B}(\vec{m})$ then any ploidy profile of the form
$(2^{n},2^{n-1},\ldots,2^{1},2^{0})$ with $n\geq 1$ is tree-child. However at
the same time an exhaustive search for the ploidy profile $\vec{m}=(3)$ shows
that not every ploidy profile is tree-child. It might therefore be interesting
to characterize tree-child ploidy profiles. This might involve better
understanding properties of the core network for $\vec{m}$ with which the
construction of $N(\vec{m})$ is initialized (see Figure 5 for two alternative
choices of a core network of the ploidy profile $(12,1)$ one of which is
$\mathcal{B}(\vec{m})$ and the other is not of the form
$\mathcal{B}(\vec{m})$). As part of this it might be tempting to first focus
on core networks obtained from a prime factor decomposition of the single
component of a strictly simple ploidy profile (see also [11] for more on
this).

## Acknowledgement

Both authors would like to thank the two anonymous reviewers for their helpful
comments to improve an earlier version of the paper.

## Data availability statement

Apart from data already publicly available (see [24]), the manuscript has no
data associated to it.

## References

  * [1] W. Albertin and P. Marullo.  Polyploidy in fungi: Evolution after whole-genome duplication.  Proc. Royal Soc. B, 279:2497–2509, 2012.
  * [2] A. Bai, P. L. Erdös, C. Semple, and M. Steel.  Defining phylogenetic networks using ancestral profiles.  Math. Biosci., 332:108537, 2021.
  * [3] M. Baroni and M. Steel.  Hybrids in real time.  Syst. Biol., 55(1):46–56, 2006.
  * [4] M. Bordewich and C. Semple.  Determining phylogenetic networks from inter-taxa distances.  J. Math. Biol., 73:283–303, 2016.
  * [5] J. J. Doyle and S. Sherman-Broyles.  Double trouble: taxonomy and definitions of polyploidy.  New Phytol., 213:487–493, 2017.
  * [6] P.L. Erdös, A. Francis, and T.R. Mezei.  Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks.  Discrete Appl. Math., 294:205–213, 2021.
  * [7] P.L. Erdös, C. Semple, and M. Steel.  A class of phylogenetic networks reconstructable from ancestral profiles.  Math. Biosci., 313:33–40, 2019.
  * [8] A. Francis and M. Steel.  Which phylogenetic networks are merely trees with additional arcs?  Syst. Biol., 64(5):768–777, 2015.
  * [9] K. T. Huber, S. Linz, and V. Moulton.  The rigid hybrid number of two phylogenetic trees.  J. Math. Biol., 82(5), 2021.
  * [10] K. T. Huber, M. Lott, V. Moulton, and A. Spillner.  The complexity of deriving a multi-labeled trees from bipartitions.  J. Comput. Biol., 15:639–651, 2009.
  * [11] K. T. Huber and L. J. Maher.  The hybrid number of a ploidy profile.  J. Math. Biol., in press.
  * [12] K. T. Huber and V. Moulton.  Phylogenetic networks from multi-labelled trees.  J. Math. Biol., 52:613–632, 2006.
  * [13] K. T. Huber, V. Moulton, and T. Wu.  Transforming phylogenetic networks: Moving beyond tree space.  J. Theor. Biol., 404:30–39, 2016.
  * [14] K. T. Huber, B. Oxelman, M. Lott, and V. Moulton.  Reconstructing the evolutionary history of polyploids from multilabeled trees.  Mol. Biol. Evol., 23:1784–1791, 2006.
  * [15] K. T. Huber and G. E. Scholz.  Phylogenetic networks that are their own fold-ups.  Adv. Appl. Math., 113:101959, 2020.
  * [16] K. T. Huber, A. Spillner, R. Suchecki, and V. Moulton.  Metrics on multilevelled trees: interrelationships and diameter bounds.  IEEE/ACM Trans. Comput. Biol. Bioinform., 8:1029–1040, 2011.
  * [17] K.T. Huber and V. Moulton.  Encoding and constructing 1-nested phylogenetic networks with trinets.  Algorithmica, 66:714–738, 2013.
  * [18] R Janssen.  Heading in the right direction? using head moves to traverse phylogenetic network space.  J. Graph Algorithms Appl., 25:263–320, 2021.
  * [19] R. Janssen and Y. Murakami.  On cherry-picking and network containment.  Theor. Comput. Sci., 856:121–150, 2021.
  * [20] G. Jones, S. Sagitov, and B. Oxelman.  Statistical inference of allopolyploid species networks in the presence of incomplete lineage sorting.  Syst. Biol., 62:467–478, 2013.
  * [21] M. Lafond, N. El-Mabrouk, K. T. Huber, and V. Moulton.  The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metric.  Theor. Comput. Sci., 760:15–34, 2019.
  * [22] R. A. Leggatt and G. K. Iwama.  Occurrence of polyploidy in the fishes.  Rev. Fish Biol. Fish., 13:237–246, 2003.
  * [23] M. Lott, A. Spillner, K. T. Huber, and V. Moulton.  PADRE: a package for analysing and displaying reticulate evolution.  Bioinformatics, 25:1199–1200, 2009.
  * [24] T. Marcussen, K. S. Jakobsen, J. Danihelka, H. E. Ballard, K. Blaxland, A.K. Brysting, and B. Oxelman.  Inferring species networks from gene trees in high-polyploid north american and hawaiian violets (viola, violaceae).  Syst. Biol., 61:107–126, 2012.
  * [25] T. Marcussen, S.R. Sandve, L. Heire, M. Spannagle, M. Pfeiffer, The international Wheat Genome Sequencing Consortium, K. S. Jakobsen, B.B.H. Wulff, B. Steuernagel, K. F. Mayer, and A.-A. Olsen.  Ancient hybridizations among the ancestral genomes of bread wheat.  Science, 345, 2014.
  * [26] J. Oldman, T. Wu, L. van Iersel, and V. Moulton.  Trilonet: Piecing together small networks to reconstruct reticulate evolutionary histories.  Mol. Biol. Evol., 33:2151–2162, 2021.
  * [27] B. Oxelman and A. Petri.  Phylogenetic relationships within silene (Caryophyllaceae) section physolychnis.  Taxon, 60(4):953–968, 2011.
  * [28] F. Pardi and C. Scornavacca.  Reconstructible phylogenetic networks: do not distinguish the indistinguishable.  PLOS Comput. Biol., 15(6):e1007137, 2015.
  * [29] C. J. Rothfels.  Polyploid Phylogenetics.  New Phytol., 230:66–72, 2021.
  * [30] J. Sardos, C. Breton, X. Perrier, I. Van den Houwe, S. Carpentier, J. Paofa, M. Rouard, and N. Roux.  Hybridization, missing wild ancestors and the domestication of cultivated diploid bananas.  Front. Plant Sci., 13:969220, 10 2022.
  * [31] C. Semple and M. Steel.  Phylogenetics.  Oxford University Press, 2003.
  * [32] C. Semple and G. Toft.  Trinets encode orchard phylogenetic networks.  J. Math. Biol., 83:Article number: 28, 2021.
  * [33] M. Steel.  Phylogeny: Discrete and Random Processes in Evolution.  SIAM, 2016.
  * [34] The Potato Sequencing Consortium.  Genome sequence and analysis of the tuber crop potato.  Nature, 475:189–195, 2011.
  * [35] L. van Iersel, R. Janssen, M. Jones, and Y. Murakami.  Orchard networks are trees with additional horizontal arcs.  Bull. Math. Biol., 84, 2022.
  * [36] L. van Iersel, R. Janssen, M. Jones, Y. Murakami, and N. Zeh.  Polynomial-time algorithms for phylogenetic inference problems.  In International Conference on Algorithms for Computational Biology, pages 37–49. Springer, 2018.
  * [37] L. van Iersel, R. Janssen, M. Jones, Y. Murakami, and N. Zeh.  A unifying characterization of tree-based networks and orchard networks using cherry covers.  Adv. Appl. Math., 129:102222, 2021.
  * [38] F. Vaoquaux, R. Blanvillain, P. Delseny, and P. Gallois.  Less is better: new approaches for seedless fruit production.  Trends in Biotechnology, 18:233–242, 2000.