Combinatorial Scoring of Phylogenetic Networks?
Nikita Alexeev

and

Max A. Alekseyev

arXiv:1602.02841v2 [q-bio.PE] 8 Aug 2016

The George Washington University, Washington, D.C., U.S.A.
Abstract. Construction of phylogenetic trees and networks for extant species from their characters
represents one of the key problems in phylogenomics. While solution to this problem is not always
uniquely defined and there exist multiple methods for tree/network construction, it becomes important
to measure how well the constructed networks capture the given character relationship across the
species.
In the current study, we propose a novel method for measuring the specificity of a given phylogenetic
network in terms of the total number of distributions of character states at the leaves that the network
may impose. While for binary phylogenetic trees, this number has an exact formula and depends only
on the number of leaves and character states but not on the tree topology, the situation is much more
complicated for non-binary trees or networks. Nevertheless, we develop an algorithm for combinatorial
enumeration of such distributions, which is applicable for arbitrary trees and networks under some
reasonable assumptions.

1

Introduction

The evolutionary history of a set of species is often described with a rooted phylogenetic tree with the species
at the leaves and their common ancestor at the root. Each internal vertex and its outgoing edges in such
a tree represent a speciation event followed by independent descents with modifications, which outlines the
traditional view of evolution. Phylogenetic trees do not however account for reticulate events (i.e., partial
merging of ancestor lineages), which may also play a noticeable role in evolution through hybridization,
horizontal gene transfer, or recombination [1,2]. Phylogenetic networks represent a natural generalization of
phylogenetic trees to include reticulate events. In particular, phylogenetic networks can often more accurately
describe the evolution of characters (e.g., phenotypic traits) observed in the extant species. Since there exists
a number of methods for construction of such phylogenetic networks [3,4], it becomes important to measure
how well the constructed networks capture the given character relationship across the species.
In the current study, we propose a novel method for measuring the specificity of a given phylogenetic
network in terms of the total number of distributions of character states at the leaves that the network
may impose. While for binary phylogenetic trees, this number has an exact formula and depends only
on the number of leaves and character states but not on the tree topology [5,6], the situation is much
more complicated for non-binary trees or network. Nevertheless, we propose an algorithm for combinatorial
enumeration of such distributions, which is applicable for arbitrary trees and networks under the assumption
that reticulate events do not much interfere with each other as explained below.
We view a phylogenetic network N as a rooted directed acyclic graph (DAG). Let N ? be an undirected
version of N , where the edge directions are ignored. We remark that if there are no reticulate events in the
evolution, then N represents a tree and thus N ? contains no cycles. On the other hand, reticulate events
in the evolution result in appearance of parallel directed paths in N and cycles in N ? . In our study, we
restrict our attention to cactus networks N , for which N ? represents a cactus graph, i.e., every edge in N ?
belongs to at most one simple cycle. In other words, we require that the simple cycles in N ? (resulting
from reticulate events) are all pairwise edge-disjoint. This restriction can be interpreted as a requirement for
reticulate events to appear in “distant” parts of the network. Trivially, trees represent a particular case of
cactus networks. We remark that some problems, which are NP-hard for general graphs, are polynomial for
cactus graphs [7], and some phylogenetic algorithms are also efficient for cactus networks [8]. We also remark
that cactus networks generalize galled trees (where cycles are vertex-disjoint) and represent a particular case
of galled networks (where cycles may share edges) [9].
We assume that the leaves (i.e., vertices of outdegree 0) of a given phylogenetic network N represent
extant species. A k-state character is a partition of the species (i.e., leaves of N ) into k nonempty sets. In
?

The work is supported by the National Science Foundation under the grant No. IIS-1462107.

1

this paper, we consider only homoplasy-free multi-state characters (see [10]), and enumerate the possible
number of such k-state characters for any particular N .

2

Methods

Let N be a cactus network. For vertices u, v in N , we say that u is an ancestor of v and v is a descendant
of u, denoted u < v, if there exists a path from u to v (possibly of length 0 when u = v). Similarly, we say
that v is lower than u, denoted u  v, if u < v and u 6= v. For a set of vertices V of N , we define a lowest
common ancestor as a vertex u in N such that u < v for all v ∈ V and there is no vertex u0 in N such that
u  u0 < v for all v ∈ V . While for trees a lowest common ancestor is unique for any set of vertices, this
may be not the case for networks in general. However, in Section 2.2, we will show that a lowest common
ancestor in a cactus network is also unique for any set of vertices.
A k-state character on N can be viewed as a k-coloring on the leaves of N , i.e., a partition of the leaves
into k nonempty subsets, each colored with a unique color numbered from 1 to k (in an arbitrary order). A
k-state character is homoplasy-free if the corresponding k-coloring C of the leaves of N is convex, i.e., the
coloring C can be expanded to some internal vertices of N such that the subgraphs induced by the vertices
of each color are rooted and connected.
Our goal is to compute the number of homoplasy-free multi-state
characters on the leaves of N , which
P∞
is the same as the total number of convex colorings p(N ) = k=1 pk (N ), where pk (N ) is the number of
convex k-colorings on the leaves of N .
2.1

Trees

In this section, we describe an algorithm for computing p(T ), where T is a rooted phylogenetic tree.
We uniquely expand each convex k-coloring of the leaves of T to a partial k-coloring of its internal vertices
as follows. For the set Li of the leaves of color i, we color to the same color i their lowest common ancestor ri
and all vertices on the paths from ri to the leaves in Li (since the k-coloring of leaves is convex, this coloring
procedure is well-defined). We call such partial k-coloring of (the vertices of) T minimal. Alternatively, a
partial k-coloring on T is minimal if and only if for each i = 1, 2, . . . , k, the induced subgraph Ti of color i
is rooted and connected (i.e., forms a subtree of T ), and removal of any vertex of Ti that is not a leaf of T
breaks the connectivity of Ti .
By construction, pk (T ) equals the number of minimal k-colorings of T .
The number pk (T ) in the case of binary trees is known [5,6] and depends only on the number of leaves
in a binary tree T , but not on its topology.
Theorem 1 ([5, Proposition
1]). Let T be a rooted binary tree with n leaves. Then the number of convex

k-colorings of T is 2n−k−1
.
Correspondingly,
p(T ) equals the Fibonacci number F2n−1 .
k−1
The case of arbitrary (non-binary) trees is more sophisticated.
Let T be a rooted tree. For a vertex v in T , we define Tv as the full subtree of T rooted at v and containing
all descendants of v.
Let T 0 be any rooted tree larger than T such that T is a full subtree of T 0 . We call a k-coloring of T
semiminimal if this coloring is induced by some minimal coloring on T 0 (which may use more than k colors).
Clearly, all minimal colorings are semiminimal, but not all semiminimal colorings are minimal. We remark
that a semiminimal k-coloring of T , in fact, does not depend on the topology of T 0 outside T and thus is
well-defined for T .
Lemma 1. A semiminimal k-coloring of T is well-defined.
Proof. Let C 0 be a minimal coloring of T 0 and C be its induced coloring on T .
If C 0 is such that T and T 0 \ T have no common colors, then C is minimal, and this property does not
depend on the topology of T 0 \ T .
If C 0 is such that T and T 0 \ T have some common color i, then the root r of T and its parent in T 0
are colored into i (hence, the shared color i is unique). Then the coloring on T ∪ {(r, l)}, where T inherits
its coloring from T 0 and l is a new leaf colored into i, is minimal. This property does not depend on the
topology of T 0 \ T either.
t
u
2

For a semiminimal k-coloring C on Tv , there exist three possibilities:
– Vertex v is colored and shares its color with at least two of its children. In this case, coloring C is minimal.
– Vertex v is colored and shares its color with exactly one of its children, and coloring C is not minimal.
– Vertex v is not colored. In this case, coloring C represents a minimal coloring of Tv .
Correspondingly, for each vertex v, we define
– fk (v) is the number of minimal k-colorings of Tv such that at least two children of v have the same color
(the vertex v must also have this color);
– gk (v) is the number of semiminimal k-colorings of Tv such that the vertex v shares its color with exactly
one of its children (i.e., semiminimal but not minimal k-colorings);
– hk (v) is the number of minimal k-colorings of Tv such that the vertex v is not colored.
We remark that the number of minimal k-colorings of T equals fk (r) + hk (r), where r is the root of the tree
T.
We define the following generating functions:
Fv (x) =

∞
X

fk (v) · xk ;

Gv (x) =

k=1

∞
X

gk (v) · xk ;

k=1

Hv (x) =

∞
X

hk (v) · xk .

(1)

k=1

For a leaf v of T , we assume fk (v) = δk,1 (Kronecker’s delta) and gk (v) = hk (v) = 0 for any k ≥ 1.
Correspondingly, we have Fv (x) = x and Gv (x) = Hv (x) = 0.
If a vertex v has d children u1 , u2 , . . . , ud , then one can compute Fv (x), Gv (x), and Hv (x) using the
generating functions at the children of v as follows.
Theorem 2. For any internal vertex v of T , we have
Hv (x) =

d
Y

(Fui (x) + Hui (x));

(2)

i=1

Gv (x) =

d
d
d
X
Y
X
Fui (x) + Gui (x)
;
(Fui (x) + Gui (x))
(Fuj (x) + Huj (x)) = Hv (x) ·
F
ui (x) + Hui (x)
j=1
i=1
i=1

(3)

j6=i


d 
Y
Fui (x) + Gui (x)
Fv (x) = x
Fui (x) + Hui (x) +
− x · Hv (x) − Gv (x);
x
i=1

(4)

where u1 , u2 , . . . , ud are the children of v.
Proof. Suppose that vertex v is not colored in a minimal k-coloring of T . Then each its child is either not
colored or has a color different from those of the other children. Furthermore, if a child of v is colored, its
color must appear at least twice among its own children. Thus, the number of semiminimal colorings of Tui
in this case is fki (ui ) + hki (ui ), where ki is the number of colors in Tui (i = 1, 2, . . . , d). Also, the subtrees Tui
cannot share any colors with each other. Hence, the number of minimal k-colorings of Tv with non-colored
v equals
d
X
Y
(fki (ui ) + hki (ui )),
k1 +···+kd =k i=1

implying formula (2).
Now suppose that vertex v is colored in a minimal k-coloring of T . Then v must share its color with at
least one of its children. Consider two cases.
Case 1. Vertex v shares its color with exactly one child, say ui . Then there are fki (ui ) + gki (ui ) semiminimal ki -colorings for Tui . For any other child uj (j 6= i), similarly to the above, we have that the number
of semiminimal kj -colorings equals fkj (uj ) + hkj (uj ). Hence, the number of semiminimal k-colorings of Tv
in this case equals
d
X
Y
(fki (ui ) + gki (ui ))
(fkj (uj ) + hkj (uj )),
j=1
j6=i

k1 +···+kd =k

3

implying formula (3).
Case 2. Vertex v shares its color with children ui , i ∈ I, |I| ≥ 2, but not with uj for j ∈
/ I. Since the
color of v is the only color shared by Tui , we have k1 + · · · + kd = k + |I| − 1. Similarly to Case 1, we get
that the number of minimal k-colorings of Tv is a coefficient at xk+|I|−1 in
Y
Y

(Fui (x) + Gui (x))
Fuj (x) + Huj (x) ,
i∈I

j ∈I
/

which is the same as the coefficient of xk in
x

Y (Fu (x) + Gu (x)) Y

i
i
Fuj (x) + Huj (x) .
x
i∈I

j ∈I
/

Summation of this expression over all subsets I ⊂ {1, 2, . . . , d} gives us the first term of (4), from where we
subtract the sum over I with |I| = 0 (the term x · Hv (x)) and with |I| = 1 (the term Gv (x)) to prove (4). t
u
2.2

Cactus Networks

In this section, we show how to compute p(N ), where N is a cactus network. The following lemma states an
important property of cactus networks.
Lemma 2. Let N be a cactus network. Then for any set of vertices of N , their lowest common ancestor is
unique.
Proof. For any set of vertices, there exists at least one common ancestor, which is the root of N .
It is enough to prove the statement for 2-element sets of vertices. Indeed, if for any pair of vertices their
lowest common ancestor is unique, then in any set of vertices we can replace any pair of vertices with their
lowest common ancestor without affecting the lowest common ancestors of the whole set. After a number of
such replacements, the set reduces to a single vertex, which represents the unique lowest common ancestor
of the original set.
Suppose that for vertices u1 and u2 in N , there exist two lowest common ancestors r1 and r2 . Let r0 be
a lowest common ancestor of r1 and r2 (clearly, r0 6= r1 and r0 6= r2 ), and P1 and P2 be paths from r0 to r1
and r2 , respectively. Then P1 and P2 are edge-disjoint. Let Qi,j be paths from ri to uj (i, j = 1, 2). It easy
to see that for each i = 1, 2, the paths Qi,1 and Qi,2 are edge-disjoint. Then the paths P1 , Q1,1 , P2 , Q2,1
form a simple cycle in N ∗ ; similarly, the paths P1 , Q1,2 , P2 , Q2,2 form a simple cycle in N ∗ . These simple
cycles share the path P1 (and P2 ), a contradiction to N being a cactus network.
t
u
In contrast to trees, cactus networks may contain branching paths, which end at vertices of indegree 2
called sinks (also known as reticulate vertices [9,2]). Clearly, there are no vertices of indegree greater than
2 in a cactus network (if there are three incoming edges to some vertex then each of them belongs to two
simple cycles in N ? ). We will need the following lemma.
Lemma 3. Let pl and pr be the parents of some sink in a cactus network N , and s be their lowest common
ancestor. Let Pl and Pr be paths from s to pl and pr , respectively. Then Pl and Pr (i) are edge-disjoint; (ii)
do not contain sinks, except possibly vertex s; and (iii) are unique.
Proof. Since s is the lowest common ancestor of pl and pr , the paths Pl and Pr are edge-disjoint.
Suppose that there is an edge (u, t0 ) on a path from s to pl such that t0 is a sink. Then this edge belongs
to two different simple cycles in N ∗ , a contradiction to N being a cactus network.
It is easy to see that if there exists a path Pl0 from s to pl different from Pl , then the paths Pl and Pl0
would share a sink (different from s), which does not exist on Pl . Hence, the path Pl is unique and so is
Pr .
t
u
Let t be a sink in N and pl and pr be its parents. Let s be the lowest common ancestor of pl and pr
(which exists by Lemma 2). Lemma 3 implies that the paths P1 and P2 from s to t that visit vertices pl
and pr , respectively, are unique and edge-disjoint. We call such a vertex s source and refer to the unordered
4

pair of paths {P1 , P2 } as a simple branching path (denoted s ⇒ t) and to each of these paths as a branch of
s ⇒ t. Notice that one source may correspond to two or more sinks in N .
For any two vertices u and v connected with a unique path in N , we denote this path by u → v (which
is a null path if v = u). A branching path between vertices p and q in N is an alternating sequence of unique
and simple branching paths
p → s1 ⇒ t1 → · · · → sm ⇒ tm → q,
where some of the unique paths may be null.
Lemma 4. For any vertices u < v in a cactus network N , the union of all paths between them forms a
branching path.
Proof. Suppose N is a cactus network and u < v in N . Let N 0 be a subnetwork of N formed by all paths
from u to v. Clearly, N 0 is a rooted (at u) cactus. We will prove that N 0 is a branching path by induction on
the number of sinks in N 0 . If there are no sinks in N 0 , then a path from u to v is unique, then the statement
holds. Otherwise, there exists a sink t in N 0 such that u  t < v and a path from t to v is unique, while
there exist multiple paths from u to t. Let s be the source in N 0 corresponding to t. Then the branching
path from s to v has the form s ⇒ t → v. Since every path from u to v visits t, it also must visit s (by
Lemma 3 a path cannot enter into a simple branching path s ⇒ t other than through vertex s). Let N 00 be
the subnetwork of N 0 consisting of all paths from u to s. Since the number of sinks in N 00 is one less than in
N 0 , by induction it is a branching path. Then N 0 is a branching path obtained from N 00 by concatenating
it with the path s ⇒ t → v.
t
u
For vertices u < v in N , the union of all paths from u to v is called the maximal branching path.
We generalize the notion of the minimal k-coloring to the case of cactus networks by expanding any
convex k-coloring of the leaves of N to a partial coloring of the internal vertices of N as follows.
Network Coloring Procedure. For a given convex k-coloring of the leaves of N , let Li be the set of the leaves
of color i. We consider maximal branching paths from the lowest common ancestor r(i) of Li to all l ∈ Li ,
which by Lemma 4 have the form:
(i)

(i)

(i)
r(i) → s1 ⇒ t1 → · · · → sm
⇒ t(i)
mi → l.
i

At the first step, we color all vertices in the unique subpaths of such maximal branching paths into color
i (Fig. 1a,b). Lemma 5 below shows that this coloring procedure (performed for all i = 1, 2, . . . , k) is welldefined. At the second step, we color some branches of simple branching subpaths of the maximal branching
(i)
(i)
paths from r(i) to the leaves in Li . Namely, for each branch between sj and tj we check if its vertices
are colored (at the first step) in any color other than i; if no other color besides i is present in the branch,
we color all its vertices into i (Fig. 1b,c). Lemma 5 below shows that at least one branch of each simple
branching subpath is colored this way, implying that the induced subgraphs of each color in the resulting
partial coloring are connected. We refer to the resulting partial coloring as a minimal k-coloring of N .
Lemma 5. For any convex k-coloring on the leaves of a cactus network N , the corresponding minimal
k-coloring of N is well-defined. Moreover, the induced subgraph of N of each color is connected.
Proof. By the definition of convexity, a given convex k-coloring of the leaves of N can be expanded to a
partial k-coloring C of N such that the induced subgraphs of each color are connected. The partial coloring
of N that we obtain at the first step is a subcoloring of C. Indeed, since the induced subgraphs of each color
in C are connected, the unique subpaths of the maximal branching paths are colored (at the first step) into
the same color as in C. Hence, no conflicting colors can be imposed at the first step.
On the second step, we color a branch in some color i only if corresponding source and sink are colored in
color i, so there are no conflicts on the second step. By Lemma 3, each non-source vertex belongs to at most
one simple branching path, and thus the second step and the whole coloring procedure are well-defined.
(i)
(i)
For any simple branching subpath sj ⇒ tj , at least one branch, say b, is colored into i in C. In the
subcoloring of C obtained at the first step, the branch b cannot contain any colors besides i. Hence, we will
color all vertices of b into i at the second step. That is, at least one branch of every simple branching subpath
will be colored, implying that the induced subgraph of each color is connected.
t
u
5

2

2

3

1

2

2

1

1

4

2

7

2

1

(a)

4

4

1

4

7

2

1

3

1

6

4

4

4

(b)

5

2

2

2

2

5

4

2

2

2

2

6

2

3

1

2

2

4

4

4

4

4

6

4

4

4

7

5

4

(c)

Fig. 1: (a) A convex coloring of the leaves of a cactus network N , where the colors are denoted by labels. (b) The
partial coloring of N constructed at the first step of the coloring procedure. (c) The minimal coloring of N .

Similarly to the case of trees, we compute p(N ) as the number of minimal colorings of a cactus network
N.
Let N 0 be any rooted network larger than N such that N is a rooted subnetwork of N 0 and all edges
from N 0 \ N to N end at the root of N . We call a k-coloring of N semiminimal if this coloring is induced
by some minimal coloring on N 0 . Similarly, to the case of trees (Lemma 1), a semiminimal k-coloring of N
does not depend on the topology of N 0 \ N and thus is well-defined.
For each vertex v in N , we define a subnetwork Nv of N rooted at v and containing all descendants of
v. An internal vertex in N is regular if the subnetworks rooted at its children are pairwise vertex-disjoint.
It is easy to see that sources in N are not regular.
For each vertex v in N , we define the following quantities:
– fk (v) is the number of minimal k-colorings of Nv such that v is colored (f -type coloring);
– gk (v) is the number of semiminimal but not minimal k-colorings of Nv (g-type coloring);
– hk (v) is the number of minimal k-colorings of Nv such that the vertex v is not colored (h-type coloring).
Our goal is to compute pk (N ) = fk (r) + hk (r) for each positive integer k, where r is the root of N . As
before, for a leaf v of N , we have fk (v) = δk,1 and gk (v) = hk (v) = 0 for any k ≥ 1. We define the generating
function Fv (x), Gv (x), and Hv (x) as in (1). Whenever we compute these functions in a subnetwork M of
M
N , we refer to them as FvM (x), GM
v (x), and Hv (x).
It is easy to see that Theorem 2 holds for all regular vertices v of N and therefore gives us a way to
compute Fv (x), Gv (x), and Hv (x), provided that these functions are already computed at the children of v.
So it remains to describe how to compute these functions at the sources in N .
Let s be a source in N and t be any sink corresponding to s. We define pl and pr be the parents of t. To
obtain formulas for Fs (x), Gs (x), and Hs (x), we consider the auxiliary subnetworks Ns , Nt , Ns\t = Ns \ Nt ,
L, R, and B (Fig. 2), where
– L is the subnetwork obtained from Ns by removing the edge (pl , t);
– R is the subnetwork obtained from Ns by removing the edge (pr , t);
– B is the subnetwork obtained from Ns by removing all the edges in the simple branching path s ⇒ t.
It is easy to see that the vertex sets of the subnetworks Ns , L, R, Nt ∪ Ns\t , and B coincide, and therefore
a partial coloring of one subnetwork translates to the others.
Lemma 6. Let t be a sink in a cactus network N and s be the corresponding source. If C is a partial coloring
of Ns of f -type, g-type, or h-type, then C contains a partial subcoloring of L or R of the same type.
6

s

pl

s

u

...

v

...

...

pr

...

t

...

pl

...

...

u

...

v

...

...

pr

...

...

t

...

Ns

s

pl

...

...

u

...

v

...

...

pr

...

...

t

...

Ns\t and Nt

s

pl

...

...

u

...

v

...

...

pr

...

...

s

t

...

L

...

...

...

R

pl

u

...

v

...

...

pr

...

t

...

...

...

...

B

Fig. 2: Subnetworks Ns , Ns\t , Nt , L, R, and B.

Proof. We say that a partial coloring of N uses an edge (u, v) if vertices u and v are colored into the same
color. Let pl and pr be the parents of t. Note that if C does not use the edge (pl , t) then it is a partial coloring
of the same type on L. Similarly, if C does not use the edge (pr , t) then it is a partial coloring of the same
type on R. So, it remains to consider the case when C uses both edges (pl , t) and (pr , t).
Suppose that C uses both edges (pl , t) and (pr , t). Notice that such C cannot be of h-type (since pr and pl
share the same color, their lowest common ancestor s has to be colored as well). So, C has f -type or g-type.
Let i be the color of t. From the second step of the coloring procedure, it follows that each vertex v such
that s < v  t is also colored into i. Hence, removal of one of the edges (pl , t) and (pr , t) does not break the
connectivity of the induced subgraph of color i. Thus, if C has f -type, then it contains a partial subcoloring
of both L and R of f -type. Now suppose that C has g-type and C 0 is a subcoloring of C constructed at the
first step of the network coloring procedure. Then at least one branch in s ⇒ t does not contain vertices of
color i in C 0 (otherwise C would have f -type). If this branch contains pl then C contains a partial subcoloring
of L of g-type; otherwise C contains a partial subcoloring of R of g-type.
t
u
Theorem 3. Let s be a source in N and t be any sink corresponding to s. Then
Ns\t

Hs (x) = HsL (x) + HsR (x) − Hs
Gs (x) =
−

GL
s (x)

+

N
Gs s\t (x)

(x) · (Ft (x) + Ht (x));

(5)

GR
s (x)
· (Ft (x) + Ht (x)) − (Ft (x) + Gt (x)) ·

Y

HvB (x);

(6)

v: s<vt
Ns\t

Fs (x) = FsL (x) + FsR (x) − Fs

(x) · (Ft (x) + Ht (x))
!
 B

Y
Fv (x) + GB
v (x)
+ HvB (x) −
HvB (x)
x
v: s<vt
s<vt
Y

− (Ft (x) + Gt (x)) ·
v:

(7)

under the following convention: if a non-leaf vertex v in N turns into a leaf in a network N 0 ∈ {Ns\t , L, R, B},
0
0
N0
then we re-define FvN (x) = GN
v (x) = 0 and Hv (x) = 1.
Proof. We say that a partial coloring of N uses an edge (u, v) if vertices u and v are colored into the same
color. Let pl and pr be the parents of t.
Let us enumerate h-type colorings of Ns first. We remark that such coloring cannot use both edges (pl , t)
and (pr , t) (if it uses both these edges, the source s would be colored by the definition of minimal coloring).
That is, any h-type coloring of Ns represents an h-type coloring of L or R, or both these networks. The
number of h-type k-colorings of L and R is the coefficient of xk in HsL (x) and HsR (x), respectively. By the
inclusion-exclusion principle, the number of h-type k-colorings of Ns equals the sum of those of L or R minus
the number of h-type k-colorings of both L and R. A coloring of the last kind does not use either of the
edges (pl , t) and (pr , t), and thus is formed by an h-type coloring of Ns\t and a minimal coloring of Nt (the
colors of the two colorings are disjoint). The number of such coloring pairs equals the coefficient of xk in
N
Hs s\t (x)(Ft (x) + Ht (x)), which completes the proof of (5).
We use similar reasoning to prove (6) and (7). The first two terms in these formulas are similar to those
in (5) that correspond to same-type colorings on L or R (at least one of which always exists by Lemma 6).
The case of colorings of g-type or f -type on both L and R is more complicated and is split into two subcases
7

depending on whether none or both of the edges (pl , t) and (pr , t) are used (if exactly one of the edges is
used, it cannot be removed without making the induced subgraph of this color disconnected). The subcase
of using none of the edges is similar to h-type colorings and gives us the third term in formulas (6) and (7).
So it remains to enumerate colorings on both L and R that use both edges (pl , t) and (pr , t).
Let C be a g-type k-coloring of Ns that is a coloring on both L and R and uses both edges (pl , t) and
(pr , t). Let C 0 be a subcoloring of C constructed at the first step of the network coloring procedure. Vertices
s and t have the same color in both C and C 0 , but any vertex v with s  v  t is colored in C but not in
C 0 . So C corresponds to a semiminimal coloring on Nt with a colored root t (i.e., of f -type or g-type) and
a coloring on B \ Nt such that vertices v with s < v  t (in Ns ) are not colored. Since B is the union of
vertex-disjoint subnetworks Nv with s < v < t, the number of such coloring pairs equals the coefficient of xk
in
Y
(Ft (x) + Gt (x)) ·
HvB (x).
v: s<vt

Now, let C be an f -type k-coloring of Ns that is a coloring on both L and R and uses both edges (pl , t)
and (pr , t). Let C 0 be a subcoloring of C constructed at the first step of the network coloring procedure.
Vertices s and t have the same color in both C and C 0 , and any vertex v with s  v  t is either colored into
the same color or not colored in C 0 . So C corresponds to a semiminimal coloring on Nt with the colored root
t (i.e., of f -type or g-type) and a coloring on B \ Nt such that at least one vertex v with s < v  t (in Ns )
is colored into the same color. The number of such colorings is the coefficient of xk in



Y
Y  F B (x) + GB (x)
v
v
+ HvB (x) −
HvB (x) .
(Ft (x) + Gt (x)) · 
x
v: s<vt

v: s<vt

The first product in the parentheses represents the generating function for the number of colorings of B \ Nt ,
where each vertex v with s < v  t (in Ns ) is either colored in a reserved color (accounted by the term
FvB (x)+GB
v (x)
)
x

or not colored (accounted by the term HvB (x)). Subtraction of the second product eliminates
the case where no vertex v with s < v  t (in Ns ) is colored.
t
u

3

Algorithm for Computing p(N )

Theorem 2 (for regular vertices) and Theorem 3 (for sources) allow us to compute the generating functions
F, G, H at the root r of a cactus network N recursively. Namely, to compute Fv (x), Gv (x), and Hv (x) for a
vertex v (starting at v = r), we proceed as follows:
– if v is a leaf, then Fv (x) = x, Gv (x) = Hv (x) = 0 (except for the special case of a newly formed leaf
described in Theorem 3, when Fv (x) = Gv (x) = 0 and Hv (x) = 1);
– if v is regular, we recursively proceed with computing Fu (x), Gu (x), and Hu (x) for every child u of v,
and then combine the results with formulae (2), (3), (4);
– if v is a source, we select any sink t corresponding to s, and apply Theorem 3 to compute Fv (x), Gv (x),
and Hv (x) from the generating functions computed in smaller subnetworks. We remark that while s may
be a source for more than one sink and thus may still remain a source in the subnetworks, the number
of sinks in each of the subnetworks decreases as compared to N , implying that our recursion sooner or
later will turn s into a regular vertex and then recursively proceed down to its children.
From the generating functions at the root r of N , we can easily obtain the number pk (N ) of convex
k-colorings of N as the coefficient of xk in Fr (x) + Hr (x). This further implies that p(N ) can be computed
as
∞
X
p(N ) =
pk (N ) = Fr (1) + Hr (1).
k=0

In the Appendix, we provide a SAGE [11] implementation of the described algorithm for computing
functions Fv (x), Gv (x), and Hv (x) for a given cactus network N and its vertex v.
8

N0

r

r

N1

N2

Fig. 3: Networks N1 and N2 represent different orientations of the same undirected network N 0 , i.e., N1? = N2? = N 0 .

4

Applications

Network Specificity. We propose to measure the specificity of a cactus network N with n leaves as a decreasing
function of p(N ). Notice that the value of p(N ) can be as small as 2n − n (for a tree with n leaves all being
children of the root) and as large as the Bell number Bn (enumerating set partitions of the leaves). We
therefore find it convenient to define the specificity score of N as
τ (N ) =

n
.
log2 (p(N ) + n)

In particular, we always have 0 < τ (N ) ≤ 1, where the upper bound is achievable. The asymptotic of Bn
log 2
further implies that τ (N ) can be asymptotically as low as log
n , which vanishes as n grows.
From Theorem 1, it can be easily seen that for a binary tree T with n leaves, we have τ (T ) ≈ log φn2n−1 ≈
0.72 when n is large, where φ =

√
1+ 5
2

2

is the golden ratio.

Network Comparison. Existing methods for construction of phylogenetic networks (e.g., hybridization networks from a given set of gene trees [4,3]) often rely on the parsimony assumption and attempt to minimize
the number of reticulate events. Such methods may generate multiple equally parsimonious networks, which
will then need to be evaluated and compared from a different perspective. It is equally important to compare
phylogenetic networks constructed by different methods. If the number of reticulate events in a constructed
network is small, it is quite likely that this network represents a cactus network. Furthermore, there exist
methods that explicitly construct phylogenetic cactus networks [8]. This makes our method well applicable
for evaluation and comparison of such networks in terms of their specificity as defined above.
Orientation of Undirected Networks. Some researchers consider undirected phylogenetic networks (called
“abstract” in the survey [2]) that describe evolutionary relationship of multiple species but do not correlate
their evolution with time. For a given undirected cactus network N 0 , our method allows one to find a root and
an orientation of N 0 , i.e., a directed rooted network N with N ? = N 0 , that maximizes the specificity score
τ (N ). Indeed, different orientations of the same undirected network may result in different scores even if they
are rooted at the same vertex. For example, in Fig. 3 the network N1 has p(N1 ) = 35 convex colorings and
the score τ (N1 ) ≈ 0.94, while the network N2 has p(N2 ) = 37 convex colorings and the score τ (N2 ) ≈ 0.927.

References
1. Holland, B.R., Huber, K.T., Moulton, V., Lockhart, P.J.: Using consensus networks to visualize contradictory
evidence for species phylogeny. Molecular Biology and Evolution 21(7) (2004) 1459–1461
2. Huson, D.H., Scornavacca, C.: A survey of combinatorial methods for phylogenetic networks. Genome Biology
and Evolution 3 (2011) 23–35

9

3. Ulyantsev, V., Melnik, M.: Constructing parsimonious hybridization networks from multiple phylogenetic trees
using a sat-solver. In Dediu, A.H., et al., eds.: Proceedings of the 2nd International Conference on Algorithms
for Computational Biology (AlCoB). Volume 9199 of Lecture Notes in Computer Science. (2015) 141–153
4. Wu, Y.: An algorithm for constructing parsimonious hybridization networks with multiple phylogenetic trees.
Journal of Computational Biology 20(10) (2013) 792–804
5. Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification 9(1) (1992) 91–116
6. Kelk, S.: A note on convex characters and Fibonacci numbers. arXiv eprint (2015) arXiv:1508.02598.
7. Korneyenko, N.: Combinatorial algorithms on a class of graphs. Discrete Applied Mathematics 54(23) (1994)
215–217
8. Brandes, U., Cornelsen, S.: Phylogenetic graph models beyond trees. Discrete Applied Mathematics 157(10)
(2009) 2361–2369
9. Huson, D.H., Rupp, R., Berry, V., Gambette, P., Paul, C.: Computing galled networks from real data. Bioinformatics 25(12) (2009) i85–i93
10. Semple, C., Steel, M.: Tree reconstruction from multi-state characters. Advances in Applied Mathematics 28(2)
(2002) 169–184
11. The Sage Developers: Sage Mathematics Software (Version 7.0). (2016) http://www.sagemath.org.

10

Appendix. SAGE Code
Below we provide a SAGE code for the function FGH(N, v), which computes the triple of functions
[Fv (x), Gv (x), Hv (x)] for a given cactus network N and its vertex v.
# Function FGH( N, v, true_leaves )
# Input:
#
N is a cactus network, possibly a subnetwork of the initial network
#
v is a vertex in N
#
true_leaves is an optional parameter, used internally,
#
set of vertices that are leaves in the initial network;
#
should be omitted when N is the initial network
# Output: [ F_v(x), G_v(x), H_v(x) ]
from itertools import combinations
def FGH( N, v, true_leaves = None ):
# test if N is a DAG
if not N.is_directed_acyclic():
raise ValueError, "Input graph is not a network!"
if true_leaves is None:
# N is a parent network, so we initialize true_leaves:
true_leaves = Set(N.sinks())
# define g.f. variable x
x = QQ[’x’].0
if N.out_degree(v) == 0:
# v is a leaf
if v in true_leaves:
return [x,0,0]
else:
return [0,0,1]
P = Poset(N)
# look for a sink in N_v if it exists
t = v
S = [ Set(P.principal_upper_set(u)) for u in N.neighbors_out(v) ]
for u in combinations(S,2):
T = u[0].intersection(u[1])
if not T.is_empty():
# sink is found
t = P.subposet(T).minimal_elements()[0]
break
if t == v:
# v is a regular vertex
# compute FGH at the children of v
cFGH = [ FGH(N,u,true_leaves) for u in N.neighbors_out(v) ]
# apply Theorem 3
H = prod(fgh[0]+fgh[2] for fgh in cFGH)
G = sum((fgh[0]+fgh[1])*H/(fgh[0]+fgh[2]) for fgh in cFGH)
F = x*prod(fgh[0]+fgh[2] + (fgh[0]+fgh[1])/x for fgh in cFGH) - x*H - G;

11

else:
# v is a source and t is a sink
t_FGH = FGH(N, t, true_leaves)
p = N.neighbors_in(t)
if len(p) != 2:
raise ValueError, "N is not a cactus network"
N.delete_edge(p[0],t)
# N represents L at this point
L_FGH = FGH(N, v, true_leaves)
N.add_edge(p[0],t)
N.delete_edge(p[1],t)
# N represents R at this point
R_FGH = FGH(N, v, true_leaves)
N.delete_edge(p[0],t)
# N represents N_{s\t} U N_t at this point
Nst_FGH = FGH(N, v, true_leaves)
# remove edges in the branching path v => t from N to form B
for q in p:
u = q
while u!=v:
w = N.neighbors_in(u)
if len(w)!=1:
raise ValueError, "Parents error w"
N.delete_edge(w[0],u)
u = w[0]
# N represents B at this point
B_FGH = [ FGH(N, u, true_leaves)
for u in Set(P.closed_interval(v,p[0])) + Set(P.closed_interval(v,p[1])) ]
B_prodH = prod(fgh[2] for fgh in B_FGH)
# apply Theorem 9
H = L_FGH[2] + R_FGH[2] - Nst_FGH[2] * (t_FGH[0] + t_FGH[2])
G = L_FGH[1] + R_FGH[1] - Nst_FGH[1] * (t_FGH[0] + t_FGH[2])
- (t_FGH[0] + t_FGH[1]) * B_prodH
F = L_FGH[0] + R_FGH[0] - Nst_FGH[0] * (t_FGH[0] + t_FGH[2])
- (t_FGH[0] + t_FGH[1]) * ( prod((fgh[0]+fgh[1])/x + fgh[2] for fgh in B_FGH) - B_prodH )
return [F,G,H]

12

