Bounding the softwired parsimony score of a phylogenetic network

The generalisation of phylogenetic trees to phylogenetic networks goes along with the development of new methods to reconstruct phylogenetic networks from genomic data. Since phylogenetic networks are structurally much more complicated than phylogenetic trees, the algorithms to infer networks are typically computationally expensive. Indeed, several optimisation problems that can be solved efficiently for phylogenetic trees, become computationally difficult for phylogenetic networks. For example, the small parsimony problem, which seeks to find the parsimony score of a given phylogenetic tree with character states assigned to its leaves is solvable in polynomial time for phylogenetic trees, e.g., using the well-known Fitch-Hartigan algorithm [7, 10], but becomes NP-hard under different notions of parsimony for phylogenetic networks, even for a single binary character and structurally constrained networks [6, 24].

Despite the popularity of model-based methods to infer phylogenetic trees, maximum parsimony (see, e.g. [4] and references therein) continues to be widely used in certain areas of evolutionary biology, such as the analysis of morphological data (see, e.g. [17, 18, 20]). Moreover, since calculating the parsimony score of a phylogenetic tree is computationally less expensive than calculating its likelihood, parsimony trees are often used as starting trees from which a search through tree space is started [23] and are also used in Bayesian phylogenetic inference [25].

Recently, different notions for parsimony on rooted phylogenetic networks have been proposed, referred to as hardwired, softwired, and parental parsimony. Softwired [16] and parental [24] parsimony both consider collections of trees that can be extracted from a rooted phylogenetic network (so-called displayed trees, respectively parental trees) and define the parsimony score as the minimum parsimony score of any tree in the collection. Softwired parsimony is implemented in the popular software package PhyloNetworks [22] and is the main focus of this paper. Hardwired parsimony [13], on the other hand, calculates the parsimony score of a phylogenetic network by considering character-state transitions along all edges of the network. As the sets of rooted phylogenetic trees that are evaluated when computing the softwired and parental parsimony scores of a phylogenetic network have exponential size, it is of interest to investigate the differences in parsimony scores of elements in these sets. Given a gap-free alignment of multi-state characters and a rooted binary level-$k$ network $N$ (formally defined below), we analyse how different the parsimony score of any phylogenetic tree displayed by $N$ and the softwired parsimony score of $N$ can be. We show that independent of the alignment length and number of character states, this difference is bounded by $k+1$ times the parsimony score of $N$. Thus, while computing the softwired parsimony score is in general an NP-hard problem (even for a single binary character and a structurally constrained network [6, Theorem 4.3]), our result implies that an upper bound for the softwired parsimony score of $N$ can be obtained in polynomial time by simply evaluating the parsimony score of an arbitrary phylogenetic tree that is displayed by $N$. In particular if the level of $N$ is small, this upper bound gives a good indication of the magnitude of the softwired parsimony score of $N$.

Related to our result, it was shown by Fischer et al. [6, Theorem 5.7] that the NP-hard optimisation problem of computing the softwired parsimony of a rooted level-$k$ network for a single multi-state character is, on the positive side, also fixed-parameter tractable, when the parameter is $k$. If one considers more than a single binary character, the softwired parsimony problem is NP-hard even for a rooted level-$1$ network [15, Theorem 1]. As a consequence of the latter negative result, Kelk et al. [15] posed the following question. Are there good (i.e. constant-factor) approximation algorithms for computing the softwired parsimony score of a rooted phylogenetic network $N$ and a sequence alignment $A$ without gaps under the following three restrictions: (i) $N$ is level-$1$, (ii) each biconnected component of $N$ has exactly three outgoing edges, and (iii) $A$ consists of binary characters?

As hinted at above, from an algorithmic perspective, our upper bound result implies a $(k+1)$-approximation algorithm for computing the softwired parsimony score of a rooted binary level-$k$ network $N$. Specifically, take an arbitrary phylogenetic tree that is displayed by $N$, compute its parsimony score, and use this to approximate the softwired parsimony score of $N$. If the level of $N$ is fixed, this algorithm provides a polynomial-time constant factor approximation. Hence, we answer the aforementioned question by Kelk et al. affirmatively for a much larger class of rooted phylogenetic networks in the sense that our result holds for level-$k$ networks (for a fixed non-negative integer $k$), it does not require restriction (ii), and it holds for gap-free alignments independent of the number of character states. Our result also complements a recent paper by Frohn and Kelk [8], in which the authors establish a 2-approximation algorithm for the softwired parsimony problem on binary tree-child networks for a single character.

While softwired parsimony for rooted phylogenetic networks is the main focus of our paper, we additionally show that an analogous upper bound for the softwired parsimony score holds for semi-directed networks that are obtained from rooted phylogenetic networks by deleting the root and omitting the direction of all but reticulation edges. Semi-directed networks have recently been central to studying identifiability questions related to phylogenetic networks and to developing phylogenetic network estimation algorithms (e.g. [1, 9, 11, 21]). We also briefly turn to the notion of parental parsimony (on rooted phylogenetic networks) and show by way of counterexample that an analogous bound for the parental parsimony score does not hold.

The remainder of this paper is organised as follows. We define all relevant concepts related to phylogenetic trees and networks, introduce the notion of softwired parsimony, and state the main result in Section 2. In Section 3, we revisit the rSPR distance and establish an upper bound on this distance for two phylogenetic trees that are both displayed by a given phylogenetic network. In Sections 4 and 5, we introduce the notion of an informative blob and a blob reduction, respectively. Informative blobs are a novel concept that is crucial for obtaining our main result, the upper bound on the softwired parsimony score, which we establish in Section 6. Sections 7 and 8 are then devoted to parental parsimony on rooted networks and softwired parsimony on semi-directed networks, respectively. We end the paper with some concluding remarks and directions for future research in Section 9.

This section introduces notation and terminology, and states the main result. Throughout this paper, $X$ denotes a non-empty finite set. Let $G$ be a directed graph. We use $V(G)$ and $E(G)$ to denote the vertex set and edge set, respectively, of $G$. Furthermore, for each edge $(u,v)$ of $G$, $u$ is called a parent of $v$ and $v$ is called a child of $u$. We sometimes also refer to $u$ and $v$ as neighbours in $G$. In a similar vein, for two (not necessarily distinct) vertices $s$ and $t$ of $G$, we say that $s$ (resp. $t$) is an ancestor (resp. descendant) of $t$ (resp. $s$) if there is a directed path of length zero or more from $s$ to $t$. Now let $G$ and $G^{\prime}$ be two directed graphs, and let $e=(u,w)$ be an edge of $G$. Then subdividing $e$ is the operation of replacing $e$ with two new edges $(u,v)$ and $(v,w)$. Furthermore, we call $G^{\prime}$ a subdivision of $G$ if $G^{\prime}$ can be obtained from $G$ by repeatedly subdividing an edge. We also consider $G$ to be a subdivision of itself.

Let $N$ be a rooted binary phylogenetic network on $X$. If $N$ has no reticulation, then it is called a rooted binary phylogenetic $X$-tree. Since all phylogenetic trees and networks are rooted and binary throughout this paper except for Section 8, we refer to a rooted binary phylogenetic network as a phylogenetic network on $X$ and to a rooted binary phylogenetic tree as a phylogenetic $X$-tree.

Let $S$ be a subdivision of a phylogenetic $X$-tree. We call the directed path from the root of $S$ to its closest degree-three vertex its root path. If $S$ is a phylogenetic tree, then the root path consists of a single edge, in which case we sometimes refer to the root path as the root edge.

Now let $N$ be a phylogenetic network. A biconnected component of $N$ is a maximal subgraph of $N$ that is connected and cannot be disconnected by deleting exactly one of its vertices. Furthermore, a vertex of a biconnected component of $N$ is called a reticulation if it is a reticulation in $N$. With this definition in hand, we say that $N$ is level-$k$ if the maximum number of reticulations of a biconnected component of $N$ is at most $k$. Lastly, we call a biconnected component of $N$ a blob if it has at least one reticulation. For a blob $B$ of $N$, we refer to the unique vertex with in-degree zero and out-degree two in $B$ as the source of $B$. A phylogenetic network $N$ on $\{x_{1},x_{2},\ldots,x_{8}\}$ with two blobs $B$ and $B^{\prime}$ is shown on the left-hand side of Figure 1.

Let $G$ be an acyclic digraph with leaf set $X$, and let $f\colon X\rightarrow C$ be a character on $X$. An extension of $f$ to $V(G)$ is a function $F\colon V(G)\rightarrow C$ such that $F(\ell)=f(\ell)$ for each element $\ell\in X$. For an extension $F$ of $f$, we set

and refer to ${\rm ch}(F,G)$ as the changing number of $F$. Intuitively, each edge of $G$ that contributes to the changing number of $F$ requires a character-state transition to explain $f$ on $G$. Lastly, we say that an extension $F$ of $f$ to $V(G)$ is minimum if there exists no extension of $f$ to $V(G)$ whose changing number is strictly smaller than that of $F$.

In what follows, we often consider a sequence $(f_{1},f_{2},\ldots,f_{n})$ of characters on $X$ instead of a single character. We call such a sequence an alignment. Unless stated otherwise, all alignments in this paper are sequences of $r$-state characters for $r\geq 2$ that do not contain the gap symbol “–”. Such an alignment is referred to as gap-free. In applied phylogenetics, multiple sequence alignments frequently contain gaps which, intuitively, are placeholders that can take on any of the other $r$ character states. We will see in the last section why the restriction to gap-free alignments is necessary. Lastly, we denote a sequence $(f_{1})$ that consists of a single element by $f_{1}$ and omit parentheses for simplicity.

Instead of calculating the parsimony score of a phylogenetic $X$-tree $T$, we are often interested in calculating the parsimony score of a subdivision of $T$ in the upcoming sections. The next lemma states that both scores are equal. Its correctness can be established analogously to the proof of Lemma 4.5 in [6]. In the proof of this lemma, Fischer et al. have shown that the softwired parsimony score of a character $f$ on a phylogenetic tree $T$ is equal to the parsimony score of $f$ on a particular rooted tree that is a generalisation of a subdivision of $T$ in the sense that it may contain unlabeled leaves in addition to the leaves in $X$.

We also have the following observation.

The next corollary positively answers the open problem that is detailed in the introduction and that was first posed in [15].

In this section, we establish an upper bound on the rSPR distance between two phylogenetic trees for when both trees are displayed by a given network. Let $N$ be a phylogenetic network, and let $R$ and $R^{\prime}$ be two switchings of $N$. We define

to be the switching distance between $R$ and $R^{\prime}$. Intuitively, $d_{\mathrm{switch}}(R,R^{\prime})$ is the number of reticulations in $N$ for which $R$ and $R^{\prime}$ contain different reticulation edges.

The following lemma is a generalisation of [3, Lemma 3.1].

To establish the main result of this paper, we introduce the novel concept of informative and non-informative blobs in this section. After giving a formal definition of these blobs, we establish results related to the changing number of character extensions to embeddings of phylogenetic trees that are displayed by phylogenetic networks that consist of a single informative or non-informative blob. Let $N$ be a phylogenetic network on $X$, and let $B$ be a blob of $N$. Furthermore, let $C_{N}(B)$ be the subset of $V(N)$ that contains precisely each vertex that is not in $B$ and that is a child of a vertex of $B$. We refer to $C_{N}(B)$, as the children of $B$. As an immediate consequence of the definition of $C_{N}(B)$, we have the following lemma that we will freely use throughout the remainder of the paper.

Now, let $s$ be the source of a blob $B$ in a phylogenetic network $N$ on $X$. Furthermore, let $S$ be an embedding of a phylogenetic $X$-tree that is displayed by $N$. Let $f$ be a character on $X$, and let $F$ be an extension of $f$ to $V(S)$. We set ${\rm ind}(F,B,S)=0$ if each element in $C_{N}(B)$ is assigned to the same character state under $F$ and, otherwise, we set ${\rm ind}(F,B,S)=1$. By Lemma 4.1, recall that each vertex in $C_{N}(B)$ is also a vertex of $S$ and, thus, ${\rm ind}(F,B,S)$ is well defined. Moreover, we say that $B$ is a non-informative blob relative to $S$ and $f$ if there exists an extension $F$ of $f$ to $V(S)$ such that $PS(f,S)={\rm ch}(F,S)$ and ${\rm ind}(F,B,S)=0$. Otherwise, we say that $B$ is an informative blob. We next extend the concept of a single informative blob to all blobs $B_{1},B_{2},\ldots,B_{m}$ of $N$ and set

where the minimum is taken over all extensions $F_{j}$ of $f$ to $V(S)$ whose changing number is equal to $PS(f,S)$. Then $b(f,N,S)$ denotes the number of informative blobs relative to $S$ and $f$ in $N$. If $F_{j}$ is an extension of $f$ to $V(S)$ such that $b(f,N,S)=\sum_{i=1}^{m}{\rm ind}(F_{j},B_{i},S)$, then we say that $F_{j}$ realises $b(f,N,S)$. See Figure 1 for an example of a phylogenetic network $N$ on $X=\{x_{1},x_{2},\ldots,x_{8}\}$ with two blobs $B$ and $B^{\prime}$, an embedding $S$ of a phylogenetic $X$-tree displayed by $N$, and a binary character $f$ on $X$ such that $b(f,N,S)=1$. Here, $B$ is non-informative because there exists a minimum extension $F$ of $f$ that assigns character state $0$ to all elements of $C_{N}(B)$, where $C_{N}(B)$ contains the source of $B^{\prime}$ and leaves $x_{7}$ and $x_{8}$. Blob $B^{\prime}$, on the other hand, is informative, as the elements in $C_{N}(B^{\prime})=\{x_{1},x_{2},\ldots,x_{6}\}$ are assigned two different states by $f$ and thus by any extension of it. To see that $F$ is indeed minimum, notice that ${\rm ch}(F,S)={\rm ch}(F,T)=1$. This is minimum since $f$ employs two states, and it is well-known and easy to see that, in this case, any extension of $f$ requires at least one change.

While Lemma 4.2 is restricted to phylogenetic networks that consist of a single non-informative blob, the next lemma establishes an analogous result for all phylogenetic networks that consist of a single blob.

In this section, we introduce the notion of a blob reduction. Intuitively, this allows us to decompose a phylogenetic network $N$ into two smaller phylogenetic networks and calculate the parsimony score of an embedding $S$ of a phylogenetic $X$-tree displayed by $N$ based on these two smaller networks.

Let $N$ be a phylogenetic network on $X$, let $B$ be a blob of $N$ whose source, say $s$, has maximum distance from the root of $N$, and let $Y=\mathrm{cl}(s)$. For some $y\notin X$, the blob reduction of $B$ reduces $N$ to two smaller phylogenetic networks as follows. Let $N(\bar{Y})$ be the phylogenetic network on $(X\setminus Y)\cup\{y\}$ that is obtained from $N$ by replacing the subnetwork of $N$ that is rooted at $s$ with a single new leaf $y$. Furthermore, let $N(Y)$ be the phylogenetic network on $Y$ that is obtained from the subnetwork of $N$ that is rooted at $s$ by adding a new vertex $\rho_{Y}$ and edge $(\rho_{Y},s)$. By construction, each of $N(\bar{Y})$ and $N(Y)$ contains at least one leaf.

Now, let $S$ be an embedding of a phylogenetic $X$-tree $T$ that is displayed by $N$. Recall that $s$ is a vertex of $S$ and $\mathrm{cl}(s)=Y$. Let $f$ be a character on $X$, and let $F$ be an extension of $f$ to $V(S)$. Using the aforementioned blob reduction of $B$ as a guide, we next also reduce $S$ to two smaller trees such that one of the resulting trees is an embedding of a subtree of $T$ in $N(\bar{Y})$ and the other one is an embedding of another subtree of $T$ in $N(Y)$. More specifically, let $S(\bar{Y})$ be the tree with leaf set $(X\setminus Y)\cup\{y\}$ that is obtained from $S$ by replacing the subtree of $S$ that is rooted at $s$ with a single new leaf $y$. Furthermore, let $S(Y)$ be the tree with leaf set $Y$ that is obtained from the subtree of $S$ that is rooted at $s$ by adding a new vertex $\rho_{Y}$ and edge $(\rho_{Y},s)$. We call $(S(Y),S(\bar{Y}))$ the cluster tree pair of $S$ relative to $B$. Let $f_{Y}$ and $f_{\bar{Y}}$ be a character on $Y$ and on $(X\setminus Y)\cup\{y\}$, respectively, such that $f_{Y}(\ell)=f(\ell)$ for each $\ell\in Y$ and $f_{\bar{Y}}(\ell^{\prime})=f(\ell^{\prime})$ for each $\ell^{\prime}\in X\setminus Y$. We refer to extensions $F_{Y}$ of $f_{Y}$ to $V(S(Y))$ and $F_{\bar{Y}}$ of $f_{\bar{Y}}$ to $V(S(\bar{Y}))$ as a pair of cluster extensions with respect to $f$ if $F_{\bar{Y}}(y)=F_{Y}(\rho_{Y})$. Except for $f_{\bar{Y}}(y)$, observe that $f$ uniquely determines the character state of each leaf in $S(Y)$ and $S(\bar{Y})$. Moreover, since the root path of $S(Y)$ contains at least one edge, the definition of a pair of cluster extensions implies that $F_{Y}(\rho_{Y})=F_{Y}(s)$ by our assumption following Observation 2.3. The next lemma shows how the changing number of extensions of characters $f$, $f_{Y}$, and $f_{\bar{Y}}$ to $V(S)$, $V(S(Y))$, and $V(S(\bar{Y}))$, respectively, are related to each other.