arXiv:1610.05068v2 [cs.DS] 21 Oct 2016

Gene Tree Construction and Correction using SuperTree and Reconciliation
Manuel Lafond

Cedric Chauve

Nadia El-Mabrouk

Département d’Informatique (DIRO)
Universié de Montréal
Montreal, QC, Canada
Email: lafonman@iro.umontreal.ca

Department of Mathematics
Simon Fraser University
Burnaby, BC, Canada
Email: cedric.chauve@sfu.ca

Département d’Informatique (DIRO)
Universié de Montréal
Montreal, QC, Canada
Email: mabrouk@iro.umontreal.ca

Aı̈da Ouangraoua
Département d’Informatique
Université de Sherbrooke
Sherbrooke, QC, Canada
Email: aida.ouangraoua@usherbrooke.ca
Abstract—The supertree problem asking for a tree displaying
a set of consistent input trees has been largely considered for
the reconstruction of species trees. Here, we rather explore this
framework for the sake of reconstructing a gene tree from a
set of input gene trees on partial data. In this perspective, the
phylogenetic tree for the species containing the genes of interest
can be used to choose among the many possible compatible
“supergenetrees”, the most natural criteria being to minimize
a reconciliation cost. We develop a variety of algorithmic
solutions for the construction and correction of gene trees using
the supertree framework. A dynamic programming supertree
algorithm for constructing or correcting gene trees, exponential
in the number of input trees, is first developed for the less
constrained version of the problem. It is then adapted to
gene trees with nodes labeled as duplication or speciation,
the additional constraint being to preserve the orthology and
paralogy relations between genes. Then, a quadratic time
algorithm is developed for efficiently correcting an initial gene
tree while preserving a set of “trusted” subtrees, as well as the
relative phylogenetic distance between them, in both cases of
labeled or unlabeled input trees. By applying these algorithms
to the set of Ensembl gene trees, we show that this new
correction framework is particularly useful to correct weaklysupported duplication nodes. The C++ source code for the
algorithms and simulations described in the paper are available
at https://github.com/UdeM-LBIT/SuGeT.

1. Introduction
The supertree problem consists in combining a set of
input phylogenetic trees on possibly overlapping sets of data,
into a single one for the whole set (see for example [1],
[2], [3], [4], [5], [6], [7]). Ideally, the obtained tree should
display each of the input trees, which is only possible if
they are “consistent” i.e. if they do not contain conflicting
phylogenetic information. The simplest formulation of the
supertree problem is therefore to state whether an input set

of trees is consistent, and if so, find a “compatible” tree,
called a supertree, displaying them all. This problem is NPcomplete for unrooted trees [8], [9], but solvable in polynomial time for rooted trees [10], [11], [12], [13]. However,
even for rooted trees the set of all possible supertrees may
be exponential in the number of genes.
Supertree methods have been mainly designed to reconstruct a species tree from gene trees obtained for various gene families. However, they can have applications
for gene tree reconstruction as well. Indeed, they may be
used to combine partial trees on overlapping gene sets
available from various sources (various databases, various
reconstruction tools, etc). Alternatively, in the case of large
gene families, they may be used to combine gene trees for
smaller sets of orthologs, usually obtained from clustering
algorithms such as OrthoMCL [14], InParanoid [15] or
Proteinortho [16]. In such a case, ideally, orthology relations
should be preserved in the final tree. More generally, given
a set of input “labeled gene trees”, i.e. gene trees with
internal nodes labeled as duplication or speciation, we may
be interested in a supertree preserving this labeling. As far
as we know, no automated method accounting for labeling
constraints has never been proposed. Here, we consider the
problem of reconstructing a “supergenetree” in both cases
of a labeled or unlabeled set of input gene trees.
In this paper, we also show that the supertree principle
can be used for gene tree correction. For various reasons
related to the considered model, method or data, gene trees
can contain many errors (see for example [17] for a link with
dubious high duplication nodes), and trees frequently exhibit
branches with low statistical support. Two main approaches
exist to correct gene trees, based on a local exploration principle to identify closely related trees that might have a better
statistical support [18], a better reconciliation cost [19], [20],
[21] or a combination of both [22], [23]. In the present work,
we consider the second approach, based on the reconciliation cost with a given species tree. A way of correcting a
gene tree is to remove weakly-supported branches, leading

to a set of subtrees, that should then be merged into a
new one, according to some criterion. The most commonly
considered criterion is a best fit with the species tree. A
simple way is to consider the set of subtrees as the leaves
of a polytomy (star-tree), and to resolve the polytomy in a
way minimizing the reconciliation cost with the species tree
(see NOTUNG [19], the Zheng and Zhang algorithm [20],
PolytomySolver [24]). Such a correction method, not only
preserves the input subtrees, but also the gene clusters
inside the subtrees. In other words, the exhibited monophily
of input gene clusters is not challenged by a polytomy
resolution method. However, it has been shown that genes
under negative selection, while exhibiting the true topology,
may be wrongly grouped into monophyletic groups (see for
example [21], [25], [26], [27]). In this perspective, using
a supertree method may be beneficial, as it preserves the
topology of subtrees while allowing to group genes from
different subtrees.
In [28], we introduced under the name of M INIMUM
S UPER G ENE T REE (M inSGT ) the problem of finding, for
a set of gene trees, a supertree that minimizes the reconciliation cost with a given species tree. Under the duplication
cost, we have shown that this problem is NP-hard to approximate within a n1− factor, for any 0 <  < 1, even
for instances in which there is only one gene per species
in the input trees, and even if each gene appears in at most
one input tree. In this paper, we carry out on M inSGT
but for the more general reconciliation cost. Although NPhardness proofs for the duplication cost do not apply to the
duplication plus loss cost, the problem is conjectured NPhard for this more general reconciliation cost, as accounting
for losses in addition to duplications is unlikely to make
the problem simpler. Given a set of consistent input gene
trees, we provide various algorithmic results depending on
the additional information we have on the trees.
In Section 3, we first exhibit a dynamic programming
algorithm for the general case, exponential in the number of
input trees. We show how this algorithm can be adapted to
compute a supertree preserving the input trees labeling, as
motivated above. In Section 4, we then consider the correction problem with as input a gene tree together with a set
of subtrees which topology should be preserved in the final
supertree. To avoid having a supertree grouping genes that
are far apart in the original tree, the relative phylogenetic
distance between gene clusters is considered as an additional
constraint. Inpired by the M INIMUM T RIPLET R ESPECTING H ISTORY introduced in [21], we define the M INIMUM
T RIPLET R ESPECTING S UPER G ENE T REE P ROBLEM asking for a supertree displaying all input subtrees, while preserving the topology of any triplet of genes taken from three
different subtrees. We develop a quadratic-time algorithm
for this problem. Finally, in Section 5, by applying these
algorithms to a set of a few hundreds Ensembl vertebrate
gene trees, we show that this new correction framework is
particularly useful to correct weakly-supported upper duplication nodes, as we observe that the correction carried out
by our algorithms often improves significantly the likelihood
scores.

2. Preliminaries
All considered trees are rooted and binary. We denote
by r(T ) the root, by V (T ) the set of nodes, and by L(T ) ⊆
V (T ) the leafset of a tree T . We say that T is a tree for
L = L(T ). Given a node x of T , the subtree of T rooted
at x is denoted T [x]. When there is no ambiguity on the
considered tree, we simply write L(x) instead of L(T [x]).
We arbitrarily set one of the two children of an internal
node x as the left child xl and the other as the right child
xr , and denote by (L(xl ), L(xr )) the bipartition induced by
x. Also for the sake of simplicity, we just denote by Tl and
Tr the left and right subtrees of the root of T . A node x is
an ancestor of a node y if x is on the path between y and
r(T ). If x is an ancestor of y , inter(x, y) is the number
of nodes located on the path between x and y , excluding x
and y . Two nodes x and y are separated in T iff none is an
ancestor of the other. In this case, we also say that the two
subtrees T [x], T [y] of T are separated.
The lowest common ancestor (lca) of L0 ⊂ L(T ),
denoted lcaT (L0 ), is the ancestor common to all leaves in
L0 that is the most distant from the root. T |L0 is the tree
with leafset L0 obtained from the subtree of T rooted at
lcaT (L0 ) by removing all leaves that are not in L0 , and
then all internal nodes of degree 2, except the root. Let T 0
be a tree such that L(T 0 ) = L0 ⊆ L(T ). We say that T
displays T 0 iff T |L0 is isomorphic to T 0 while preserving
the same leaf-labeling.
Gene and species trees. A species tree S for a set Σ of
species represents an ordered set of speciation events that
have led to Σ. A gene family is a set of genes Γ accompanied
with a mapping function s : Γ → Σ mapping each gene to
its corresponding species. Consider a gene family Γ where
each gene x ∈ Γ belongs to a species s(x) of Σ. The
evolutionary history of Γ can be represented as a gene tree
G for Γ. For example, in Figure 1, G is a gene tree for
Γ = {s1 , s2 , b1 , b2 , h1 , h2 , h3 , m3 , r3 }. Each internal node
of G refers to an ancestral gene at the moment of an event,
either speciation (Spec) or duplication (Dup). The mapping
function s is generalized as follows: if x is an internal node
of G, then s(x) = lcaS ({s(x0 ) : x0 ∈ L(x)}).
When the type of event is known for each internal node,
the gene tree G is said labeled. Formally, a labeled gene tree
for Γ is a pair (G, evG ), where G is a tree for L(G) = Γ, and
evG : V (G) \ L(G) → {Dup, Spec} is a function labeling
each internal node of G as a duplication or a speciation
node.
According to the Fitch [29] terminology, given a labeled gene tree (G, evG ), we say that two genes x, y are
orthologs if evG (lcaG (x, y)) = Spec, and paralogs if
evG (lcaG (x, y)) = Dup. For example, from the set of
labeled gene trees in Figure 1, s1 , h1 are orthologs while
s1 , h2 are paralogs.
While a history for Γ can be represented as a labeled
gene tree, the converse is not always true, as a labeled
tree (G, evG ) for Γ does not necessarily represent a valid
history in agreement with a species tree S . For this to hold,

Figure 1. A species tree S on Σ = {s, b, h, m, r}, and a set of labeled gene trees G = {G1 , G2 , G3 , G4 }, where each leaf xi denotes a gene belonging
to x. Square nodes are duplications and circular nodes are speciations. Internal nodes are labeled according to corresponding ancestral species in S . Dotted
lines are losses. G is a supergenetree for G of minimum LCA-reconciliation cost (cost of 3), while G0 is a label-compatible supergenetree for G of
reconciliation cost 8 (3 duplications + 5 losses). G is not a label-compatible supergenetree due to the roots of G2 and G3 which are duplications in G2
and G3 (green squares), but are mapped to a speciation node in G (green circle). In G0 , these nodes are correctly mapped to duplication nodes (green
squares in G0 ).

(G, evG ) should be S -consistent, i.e. any speciation node
of (G, evG ) should reflect the same clustering of species as
in S (see [30] for a formal definition of S -consistency).

Reconciliation. The LCA-reconciliation of G with S is the
labeled tree (G, evG ) obtained by labeling each node x of G
as Spec if and only if s(xl ) and s(xr ) are separated in S , and
as Dup otherwise. It follows that the LCA-reconciliation of
G with S is an S -consistent tree. In Figure 1, G is labeled
according to the LCA-reconciliation.
Given a labeled gene tree (G, evG ), the duplication cost
of (G, evG ) is its number of duplication nodes. It reflects
the number of duplications required to explain the evolution
of the gene family inside the species tree S according to
G. A well-known reconciliation approach [19], [31], [32]
allows to further recover, in linear time, the minimum
number of losses underlined by such an evolutionary
history. We refer to the number of duplications and losses
underlined by a labeled gene tree as its reconciliation cost
in the general case, and as its LCA-reconciliation cost if
the tree is labeled according to the LCA-reconciliation.
Supertree problems. Given a set G of trees for possibly
overlapping subsets of Γ, the goal is to find a single tree
displaying them all. This is possible only if the input trees
are pairwise consistent. The consistency problem of rooted
trees has been largely studied. For trees to be consistent,
each triplet of data should exhibit the same topology in
all trees. The BUILD algorithm [10] can be used to test,
in polynomial-time, whether a collection of rooted trees is
consistent, and if so, construct a compatible, not necessarily
fully resolved, supertree. This algorithm has been generalized to output all compatible supertrees [11], [12], [13],
which may be exponential in the number of genes.

3. Algorithms for Minimum SuperGeneTree
Problems
We begin with the less constrained version of the
problem. Given a set G of consistent input gene trees,
we ask for a compatible tree, also called supergenetree G
for G , i.e. a tree displaying each tree of G . In addition,
among all supergenetrees for G , G should be of minimum
LCA-reconciliation cost (see G in Figure 1).
M INIMUM S UPER G ENE T REE (M inSGT ) P ROBLEM :
Input: A species set Σ and a species tree S for Σ; a gene
family Γ of size n, a set Γi,1≤i≤k of subsets of Γ such that
Sk
i=1 Γi = Γ, and a consistent set G = {G1 , G2 , · · · , Gk }
of gene trees such that, for each 1 ≤ i ≤ k , Gi is a tree for
Γi .
Output: Among all trees G for Γ compatible with G , one
of minimum LCA-reconciliation cost.
Suppose now that the input trees are labeled, and consider this labeling as an additional constraint. The problem
becomes one of finding a labeled supergenetree preserving
the input gene trees node labeling. As a labeled gene tree
induces a full orthology and paralogy relation on the set
of its leaves, this is possible only if the set of relations is
satisfiable, i.e. if there is a labeled tree (G, evG ) displaying
the relations induced by all the input trees, and if there is
such a tree which is S -consistent. Satisfiability is a wellstudied problem. It reduces to verifying if a relation graph
R (vertices are genes and edges link orthologous genes) is
P4 -free, i.e. no four vertices of R induce a path of length
3 [33]. On the other hand, a cubic-time algorithm was
developed in [30] for deciding whether a set of relations is
S -consistent. Hereafter, we assume that the relations induced

by the input trees are satisfiable and S -consistent.
Let G and G0 be two trees with L(G0 ) ⊆ L(G) such
that G displays G0 . Then (G, evG ) is said label-compatible
with (G0 , evG0 ) iff, for any internal node x of G and x0
of G0 such that x = lcaG (L(x0 )), evG (x) = evG0 (x0 ).
A labeled supergenetree G for a set G of trees is said
label-compatible with G iff it is label-compatible with each
of the labeled trees of G . An illustration is provided by
the supergenetree G0 in Figure 1. We are now ready to
formulate our second problem.
M INIMUM L ABELED S UPER G ENE T REE (M inLSGT )
P ROBLEM :
Input: A species set Σ and a species tree S for Σ;
a gene family Γ of size n, a set Γi,1≤i≤k of subsets
Sk
of Γ such that
i=1 Γi = Γ, and a consistent set
G = {(G1 , ev1 ), (G2 , ev2 ), · · · , (Gk , evk )} of satisfiable
and S -consistent labeled gene trees where, for each
1 ≤ i ≤ k , Gi is a tree for Γi .
Output: Among all labeled supergenetrees (G, evG ) for Γ
label-compatible with G , one of minimum reconciliation
cost.
The M inSGT and M inLSGT problems for the duplication cost were both shown NP-Hard in [28], even in the
case where no two input trees have a gene in common and
the trees only contain speciations.

3.1. The M inSGT problem
We describe a dynamic programming algorithm for the
M inSGT problem leading to the following result.
Theorem 1. The M inSGT problem can be solved in
O((n + 1)k × 4k × k) time complexity.
The algorithm constructs the supergenetree G from the
root to the leaves. At each step, i.e. for each internal
node x being constructed in G, all possible bipartitions
(L(xl ), L(xr )) that could be induced by x are tried, and
the iteration continues on each of L(xl ) and L(xr ). For
example, at the root, the goal is to find the best bipartition of
Γ, i.e. the one leading to the minimum LCA-reconciliation
cost. At each step, this cost is computed from a local
reconciliation cost at x (as defined in Lemma 1), and from
the best reconciliation cost of the two created clusters. A
key observation is that the constraint of being compatible
with the input gene trees induces a strong constraint on the
bipartitions, hence only a subset of the bipartition set has to
be tested at each step.
First, a formulation of the reconciliation cost in terms
of the sum of local reconciliation costs at each internal
node x is given. The next lemma is a reformulation of the
reconciliation cost, as described in many papers [19], [32].
Lemma 1. The LCA-reconciliation cost of a gene tree G is
the sum of local LCA-reconciliation costs cost(Ll , Lr ) for
all internal nodes x of G, where L = L(x), and (Ll , Lr ) =
(L(xl ), L(xr )), and cost(Ll , Lr ) equals to:

•
•
•

inter(s(L), s(Ll )) + inter(s(L), s(Lr ))
if s(L) 6= s(Ll ) and s(L) 6= s(Lr );
1 + inter(s(L), s(Ll )) + inter(s(L), s(Lr ))
if s(L) = s(Ll ) and s(L) = s(Lr );
2 + inter(s(L), s(Ll )) + inter(s(L), s(Lr ))
if s(L) = s(Ll ) and s(L) 6= s(Lr ) or conversely.

The node x = (Ll , Lr ) is a speciation node in the first
case, and a duplication node in the two last cases (thus
adding 1 duplication to the LCA-reconciliation cost, plus 1
loss in the third case). Note that inter(s, t) = 0 if s = t.
For example, the root of G in Figure 1 fulfills the
conditions of the first case, and thus it is a speciation node,
whereas the root of G0 fulfills the condition of the third case.
Lemma 1 allows to recursively compute a minimum
LCA-reconciliation cost supergenetree, by exploring, for
each node x from the root to the leaves, all “valid” bipartitions of L(x), remaining to be characterized formally. In the
following, we define the properties of a bipartition (Ll , Lr )
induced by the root of a supergenetree G. It directly follows
from the definition of a supergenetree that should display
each individual gene tree.
Property 1. Let G = {G1 , . . . , Gk } be a set of gene trees.
The
Sk root of a supergenetree G compatible with G subdivides
i=1 L(Gi ) into a compatible bipartition (Ll , Lr ), i.e. a
bipartition such that, for each i s.t. 1 ≤ i ≤ k , either: 1)
L(Gi ) ⊆ Ll ; or 2) L(Gi ) ⊆ Lr ; or 3) L(Gil ) ⊆ Ll and
L(Gir ) ⊆ Lr ; or 4) L(Gil ) ⊆ Lr and L(Gir ) ⊆ Ll .
For example, the root of the supergenetree G in Figure 1
satisfies the third condition for G1 , G2 and G3 , and the
second for G4 .
Sk B(G1 , . . . , Gk ) denotes the set of all bipartitions of
i=1 L(Gi ) compatible with G . For example, the two bipartitions defined by the roots of G and G0 in Figure 1 are
both compatible with the given set of gene trees. Figure 2
illustrates the set of all valid bipartitions compatible with
two given trees.
k

Lemma 2. |B(G1 , . . . , Gk )| ≤ ( 42 ) − 1.
Proof. For each tree Gi , there are four possibilities for
placing L(Gir ) and L(Gil ) in a bipartition (Ll , Lr ): either
they are both in Ll , or both in Lr , or one in Ll and the
other in Lr . Therefore, 4k distributions of left and right
subtrees of the k trees in (Ll , Lr ). However, as the left and
right characterization of nodes is arbitrary, each distribution
is counted twice,
and thus the total number of different
k
bipartitions is 42 . One of these bipartitions has a part that
k
is empty. We discard it and the total number is then 42 − 1.
However, a set (Ll , Lr ) obtained from such distribution of
the Gi subtrees is not necessarily a bipartition, as a same
gene can be present in two different input trees, and end up
k
placed in both Ll and Lr . Therefore, ( 42 ) − 1 is only an
upper bound of the number of compatible bipartitions.
The constructive proof of Lemma 2 induces an algorithm
for enumerating the members of B(G1 , . . . , Gk ), which is

G = {G1, G2}
G1

G1,l

B(G1, G2)
G1

G2

G1,l

G1,r
G1 G2,l

G2

G1,r

G1,l G2,l

G1,r G2,r

G1,l G2,r

G1,r G2,l

G2,r

G2
G1,l

G2,l

G2,r

G1 G2,r

G1,r

G2

G2,l

Figure 2. An illustration of the seven valid bipartitions for two trees G1 and G2 . Each bipartition is obtained by “sending” L1 ∈
{L(G1 ), L(G1,l ), L(G1,r ), ∅} in the left part, and the complement L(G1 ) \ L1 in the right part. The same process is then applied to G2 . The
set B(G1 , G2 ) consists in the set of all possible combinations of choices, after eliminating symmetric cases and partitions with an empty side. For each
bipartition (Ll , Lr ) of B(G1 , G2 ), an optimal solution is recursively computed for Ll and Lr , the reconciliation cost is computed for the tree obtained
by joining the roots of the two trees under a common parent, and the tree yielding a minimum cost among all possibilities is returned.

illustrated in Figure 2 for the case of two trees. Intuitively,
to construct a bipartition (Ll , Lr ), each tree Gi of G can
choose to “send” in Ll either its left subtree Gil , its right
subtree Gir , the whole tree Gi or nothing at all. What has
not been sent in Ll is sent in Lr . Then B(G1 , . . . , Gk ) is
the set of all possible combinations of choices. However, not
every bipartition constructed in this manner yields a valid
bipartition. For instance in Figure 2, the top-left bipartition
cannot be valid if G1 and G2 share a leaf with the same
label, as a gene cannot be sent both left and right. These
cases, however, can be detected easily by verifying the sizes
of Ll and Lr .
We are now ready to give the main recurrence formula of our dynamic programming algorithm. Denote by
M inSGT (G1 , . . . , Gk ) the minimum LCA-reconciliation
cost of a supergenetree compatible with G = {G1 , . . . , Gk }.
The next lemma directly follows from Lemma 1 and Property 1.
Lemma 3. Let G = {G1 , . . . , Gk } be a set of gene trees.
Sk
1) M inSGT (G1 , . . . , Gk ) = 0 if | i=1 L(Gi ) | = 1
(Stop condition);
2) Otherwise, M inSGT (G1 , . . . , Gk ) =


 cost(Ll , Lr )+

M inSGT (G1|Ll , . . . , Gk|Ll )+
min
(Ll ,Lr )∈B(G1 ,...,Gk ) 
M inSGT (G1|Lr , . . . , Gk| Lr ) 
Note that, given a bipartition (Ll , Lr ) ∈ B(G1 , . . . , Gk ),
for each i such that 1 ≤ i ≤ k , Gi|Ll and Gi|Lr are equal
either to ∅ or Gi or Gil or Gir . Thus, Gi|Ll and Gi|Lr are
either empty trees or complete subtrees of Gi .
Note also that, at each step, the existence of a
compatible bipartition follows from the fact that the input
gene trees are assumed to be consistent, as stated in the
formulation of the M inSGT problem. In the absence of this
assumption,
we have to add a third equation to Lemma 3:
Sk
If |
L(G
i ) | > 1 and | B(G1 , . . . , Gk ) | = 0,
i=1
M inSGT (G1 , . . . , Gk ) = +∞.

Complexity. We now address the complexity of the dynamic programming algorithm defined by the recurrences of
Lemma 3. Each call to the recursive procedure M inSGT
receives as input at most one subtree from each tree Gi .
Let n be the maximum number of node in a tree Gi .
As each tree has at most n possible subtrees, there are
at most (n + 1)k possible calls to M inSGT . Next, for
any set of gene trees {G1 , . . . , Gk }, the number of distinct
bipartitions (Ll , Lr ) ∈ B(G1 , . . . , Gk ) to be tested is at
k
most 42 − 1 (Lemma 2). Finally, the value of cost(Ll , Lr )
can be computed in time O(k) provided that the mapping
s is precomputed for all nodes of the trees G1 , . . . , Gk ,
and lca(x, y) and inter(x, y) are precomputed for any pair
(x, y) of nodes in S . The time complexity of the overall
algorithm is therefore O((n+1)k ×4k ×k), which completes
the proof of Theorem 1.

3.2. The M inLSGT Problem
The algorithm for the M inSGT problem can be adapted
to solve the M inLSGT problem, leading to the following
result.
Corollary 1. The M inLSGT problem can be solved in
O((n + 1)k × 4k × k) time complexity.
The intuition behind the M inLSGT algorithm is quite
simple. We proceed as in the M inSGT algorithm, but each
time a bipartition (Ll , Lr ) is considered, we verify whether
the root of a tree separating Ll and Lr should be a speciation
or a duplication. If there are two genes gl ∈ Ll and gr ∈ Lr
that disagree with this event, we treat (Ll , Lr ) as an invalid
bipartition and do not consider it further.
Before describing this adaptation, we need few additional definitions and properties. Given a set of labeled gene
trees G = {(G1 , evG1 ), . . . , (Gk , evGk )} and a bipartition
(Ll , Lr ) ∈ B(G1 , . . . , Gk ), for any i s.t. 1 ≤ i ≤ k , we say
that Gi is separated by (Ll , Lr ) iff Gi satisfies the third
or fourth condition of Property 1. We denote by G(Ll , Lr )

the set of gene trees Gi , 1 ≤ i ≤ k , that are separated by
(Ll , Lr ).
Lemma 4. Let G = {(G1 , evG1 ), . . . , (Gk , evGk )} be a set
of labeled gene trees. Then, for any labeled supergenetree
(G, evG ) label-compatible with G , the label evG (x) of its
root x equals the label of the root of any gene tree Gi ,
1 ≤ i ≤ k , such that Gi ∈ G(L(xl ), L(xr )).
Proof. Let Gi , 1 ≤ i ≤ k be a genetree such that
Gi ∈ G(L(xl ), L(xr )), and let xi be the root of Gi .
Then lcaG (L(xi )) = x, and thus by definition of the
label-compatibility of G with Gi , we have evG (x) =
evGi (xi ).
Sk
From Lemma 4, we define a bipartition of i=1 L(Gi )
label-compatible with G as follows.
Definition 1. Let G = {(G1 , evG1 ), . . . , (Gk , evGk )} be
a
Skset of labeled gene trees. A bipartition (Ll , Lr ) of
i=1 L(Gi ) is label-compatible with G if it is compatible
with G and verifies:
1)
2)

if | G(Ll , Lr ) | > 0, the roots of all gene trees
in G(Ll , Lr ) have the same label denoted by
evG(Ll ,Lr ) .
if | G(Ll , Lr ) | > 0 and evG(Ll ,Lr ) = Spec, then
lcaS ({s(x) : x ∈ Ll ∪ Lr }) 6= lcaS ({s(x) :
x ∈ Ll }) and lcaS ({s(x) : x ∈ Ll ∪ Lr }) 6=
lcaS ({s(x) : x ∈ Lr }).

For example, the bipartition determined by the root of
the supergenetree G ({s1 , s2 , b1 , b2 }, {h1 , h2 , h3 , m3 , r3 })
in Figure 1 is not label-compatible with the set of gene
trees, as it separates both G1 and G2 which do not have the
same root label.
The M inLSGT algorithm for solving the M inSGT
problem is based on the same general dynamic programming
framework as the M inSGT algorithm: at each step, iterate
over all possible bipartitions, and then proceed recursively
for each partition. The two differences are: (1) given a set of
labeled gene trees G = {(G1 , ev1 ), . . . , (Gk , evk )}, we only
test a subset of compatible bipartitions of B(G1 , . . . , Gk )
that are label-compatible with G ; (2) computing local reconciliation costs should not be done on the basis of the LCAreconciliation, as some nodes that would be labeled as speciation nodes from the LCA-mapping should rather be duplication nodes in order to be label-compatible with some input
gene trees. For example, in Figure 1, lcaG0 ({s2 , b2 , h2 })
would be labeled Spec by the LCA-mapping. However, it
should be labeled Dup to be label-compatible with G3 . The
following Lemma is required, in place of Lemma 1.
Lemma 5. Let x be an internal node of a labeled supergenetree (G, evG ), L = L(x) and (Ll , Lr ) = (L(xl ), L(xr )).
The local reconciliation cost of x, costG (Ll , Lr ) is equal
to:
•

3 + inter(s(L), s(Ll )) + inter(s(L), s(Lr )) if
s(L) 6= s(Ll ), s(L) 6= s(Lr ), | G(Ll , Lr ) | > 0
and evG (Ll , Lr ) = Dup;

•

cost(Ll , Lr ) Otherwise.

In the first case, the node x is a duplication node adding
1 duplication plus at least 2 losses to the reconciliation
cost, and in the second case the local reconciliation cost is
computed as for the LCA-reconciliation.
The complexity of the M inLSGT algorithm remains
in O((n + 1)k × 4k × k) provided that the sets of labelcompatible bipartitions (Ll , Lr ) are constructed simultaneously with the sets G(Ll , Lr ).

3.3. Improved complexity from a core set of trees
Last, we show that the principles underlying the two
algorithms described above can be improved to reduce the
dependency in k . The key remark is that all bipartitions to
consider can be identified by considering only a subset of
the input trees provided they span the
S set of all genes of Γ.
Call G 0 ⊆ G a core of G if G∈G 0 L(G) = Γ. We
introduce the following modified M inSGT algorithm, that
we call M inSGT -core:
1)
2)

Find a core G 0 = {G01 , . . . , G0` } of G .
Apply the M inSGT algorithm on G 0 , with the
exception that, when considering a bipartition B =
(Ll , Lr ) compatible with G 0 :
• Verify that B is also compatible with G \ G 0 . If
not, then do not proceed recursively on B ;
• Compute cost(Ll , Lr ) on the whole set G .

Theorem 2. Let G 0 be a core of G composed of k00 trees.
The
0
M inSGT problem can be solved in O((n + 1)k × 4k × k)
time complexity.
Proof. The difference between the executions of a call of the
M inSGT -core algorithm on the input G 0 and a call of the
M inSGT on G lies in the set of bipartitions considered at
each step of the recursion. At a given step of the recursion,
let B 0 and B be the set of bipartitions compatible with G 0
and G respectively, and let B ∗ be the set of bipartitions
considered by M inSGT -core. We show that B = B ∗ .
Clearly B ⊆ B 0 , as a bipartition compatible with G
is also compatible with G 0 ⊆ G . Suppose that there is
some (Ll , Lr ) ∈ B such that (Ll , Lr ) ∈
/ B ∗ . This implies
0
that (Ll , Lr ) was filtered out of B , meaning that it is not
compatible with some tree G ∈ G \ G 0 . Therefore (Ll , Lr )
cannot be in B , a contradiction. We deduce that B ⊆ B ∗ . To
see that B ∗ ⊆ B , observe that B ∗ contains only bipartitions
compatible with G 0 ∪(G \G 0 ) = G , and that B contains every
such bipartition. So both algorithms consider the same set of
bipartitions at each step, and lead to the same solution.
It thus remain to describe how to find a core G 0 , as
small as possible, as the size of the core is now the main
complexity parameter. This problem is equivalent to the
M INIMUM S ET C OVER P ROBLEM known to be NP-hard.
However, a natural heuristic is the following: choose a gene
tree Gi with the largest subset of Γ as leafset, say of size
n−p, and “complete” it with at most p additional gene trees

The same technique applies to M inLSGT and the same
result could be stated for this problem.

the set of subtrees G of GInit augmented with the set of all
rooted triplet trees that should be respected by the output
supergenetree. However, the algorithms for M inT RS and
M inLT RS problems induced by these reductions would
remain exponential in the number of input subtrees.
We describe a more efficient recursive algorithm that
solves the M inT RS problem by making use of the
M inSGT solution. This algorithm leads to the following
result.

4. Triplet Respecting Supergenetrees

Theorem 3. The M inT RS and M inLT RS problems can
be solved in O(n2 ) time complexity.

We now consider a problem related to the correction of
a gene tree. Assume that input gene trees G1 , G2 , · · · , Gk
are separated subtrees (i.e. leaf-disjoint) of a given gene tree
GInit . The M inSGT and M inLSGT problems can also be
considered in this context to infer an alternative gene tree
displaying them all and minimizing a reconciliation cost.
However, this may lead to a new tree exhibiting a complete
reorganization of the input subtrees and possibly grouping
genes that were far apart in the initial tree. Therefore,
assume in addition that we trust the hierarchy of upper
branches. Then we ask for a supergenetree of minimum
reconciliation cost which preserves the phylogenetic relation
between subtrees, as given by GInit . Formally, we seek for
a triplet respecting supergenetree, as defined bellow.

The high-level description of the algorithm is as follows.
The triplet-respecting property only allows a limited number
of ways to combine the subtrees of G together. We distinguish two possible cases. First, if two subtrees G1 , G2 of G
form a “cherry” in GInit , meaning that r(G1 ) and r(G2 )
share the same parent in GInit , then G1 and G2 can be
mixed together in any way without contradicting the tripletrespecting property. The optimal way of mixing the two trees
is to compute M inSGT (G1 , G2 ), which gives a solution
for the subtree of GInit rooted at the parent of r(G1 ) and
r(G2 ). For instance in Figure 3, the two children of the β
node in GInit form a cherry of subtrees. Second, if instead
a subtree G1 of G is not part of such a cherry, then let x
be the sibling of r(G1 ) in GInit . Then we show that the
following procedure can be performed: recursively compute
Gx , an optimal solution for the subtree of GInit rooted at
x, then try grafting Gx on G1 in every possible way and
keep the solution that minimizes the reconciliation cost. This
gives a solution for the subtree of GInit rooted at the parent
of r(G1 ) and x. These two cases describe all the possible
subtree mixings that can occur, and the rest of the GInit
topology must be conserved. For example in Figure 3, from
a bottom-up point of view, the algorithm would compute
G3,4 = M inSGT (G3 , G4 ), then obtain G2,3,4 by finding
the best place on which to graft G3,4 on G2 (in this case,
above the parent of m1 and r1 ), then obtain a solution by
grafting G2,3,4 somewhere on G1 (in this case above h1 ).
In the following we rather describe the algorithm in a topdown manner, i.e. we start at the root of GInit , obtain a
solution recursively for its two child subtrees and combine
them appropriately.
Before describing the algorithm in full detail, we give
a few additional definitions and properties. Let G and
G0 be two gene trees for Γ. Define sG0 →G as the mapping from the nodes of G0 to the nodes of G such that
sG0 →G (x) = lcaG (L(x)). For example in Figure 3, the
image of the green-colored node of GInit by sGInit →G is
the green-colored node of G.
The algorithm for M inT RS constructs the triplet respecting supergenetree GT R by building recursively and
independently the bipartitions (L(yl ), L(yr )) induced by
each internal node y of GT R from the root to the leaves.
The nodes of GT R can be considered independently in the
algorithm because the constraint of being triplet respecting
strongly predetermines the set of leaves L(y) associated to
some nodes y of GT R as shown in Lemma 6.

from G each containg at least one of the missing genes. This
obviously provide a core, leading to the following result.
Corollary 2. The M inSGT problem can be solved in
O((n + 1)p+1 × 4p+1 × k) time complexity, where p is the
smallest integer such that a gene tree of G contains n − p
genes.

Definition 2. Let G = {G1 , G2 , · · · , Gk } be a set of
separated
subtrees of a gene tree GInit for Γ such that
Sk
TR
compatible with G is triplet
i=1 L(Gi ) = Γ. A tree G
respecting iff, for any triplet of trees L(Gi1 ), L(Gi2 ) and
L(Gi3 ) in G and any triplet of genes x ∈ Gi1 , y ∈ Gi2 and
z ∈ Gi3 , GInit and GT R display the same topology for the
triplet (x, y, z), i.e. GInit |{x,y,z} = GT R |{x,y,z} .
For example in Figure 3, the supergenetree G is not
triplet respecting as for the triplet of genes (h1 , m1 , m2 ),
G does not display the same topology as the tree GInit .
M INIMUM T RIPLET R ESPECTING S UPERGENETREE
(M inT RS ) P ROBLEM :
Input: A species set Σ and a species tree S for Σ;
a gene family Γ and a gene tree GInit for Γ; a set
G =S
{G1 , G2 , · · · , Gk } of separated subtrees of GInit such
k
that i=1 L(Gi ) = Γ.
Output: Among all triplet respecting gene trees for Γ
compatible with G , one of minimum LCA-reconciliation
cost.
A natural extension of the M inT RS Problem is the
M INIMUM L ABELED T RIPLET R ESPECTING S UPERGENE TREE ( M inLT RS ) Problem, where we are given a set of
labeled separated subtrees of GInit and we seek for a labeled
triplet respecting supergenetree of minimum reconciliation
cost. Here we focus on M inT RS , though all results extend
naturally to M inLT RS , as briefly explained at the end of
this section. Note that the M inT RS and M inLT RS problems can be reduced to the M inSGT and M inLSGT problems by considering as input of M inSGT and M inLSGT

Figure 3. A species tree S on the set of species Σ = {s, b, h, m, r}, and a gene tree GInit with a set of separated subtrees G = {G1 , G2 , · · · , G4 }.
The name of genes, the form and color of internal nodes and lines follow the same rules as in Figure 1. G is a supergenetree for G of minimum
LCA-reconciliation cost (cost of 2) and GT R is a triplet respecting supergenetree for G of LCA-reconciliation cost 4 (3 duplications + 1 loss). G is not a
triplet respecting supergenetree because for example, for the triplet of genes (h1 , m1 , m2 ) in red color, GInit displays the topology (h1 , m1 m2 ) while
G displays the topology (h1 m1 , m2 ). In GT R however, all triplet genes topologies are respected.

Given a node x of GInit , we denote by G(x) the subset
of G that are subtrees of GInit [x]. If there exists a node y
in GT R such that L(y) = L(x), then we also define G(y) =
G(x). For example, call x the white-colored node of GInit in
Figure 3. Then G(x) = {G2 , G3 , G4 }. Now, for y being the
white-colored node of GT R , L(y) = L(x) and so G(y) =
{G2 , G3 , G4 }.
Lemma 6. Let GT R be a triplet respecting supergenetree
for GInit and G = {G1 , . . . , Gk }. For any node x of GInit
such that | G(x) | ≥ 2, there exists a node y of GT R such
that L(y) = L(x).
Proof. Let x be a node of GInit such that | G(x) | ≥ 2.
Each of the subtrees GInit [xl ] and GInit [xr ] then contains
at least one tree of G . Assume that (*) there exists no node
y in GT R such that L(y) = L(x). Let x0 be the node of
GT R such that sGInit →GT R (x) = x0 , and let x00 be the node
of GInit such that sGT R →GInit (x0 ) = x00 . The assumption
(*) implies that x00 6= x, so x00 is a strict ancestor of x.
Suppose w.l.o.g. that x belongs to the subtree GInit [x00l ] and
pick any gene c ∈ L(x0 ) ∩ L(x00r ). There exists a tree Gh of
G such that c ∈ L(Gh ) and Gh is contained in GInit [x00r ].
Now, let a and b be two genes such that a ∈ L(xl ) ∩ L(x0l )
and b ∈ L(xr ) ∩ L(x0r ), or a ∈ L(xl ) ∩ L(x0r ) and b ∈
L(xr ) ∩ L(x0l ). Such two genes necessarily exist because
sGInit →GT R (x) = x0 . So, there exist two trees Gi and Gj
of G such that (a, b) ∈ L(Gi ) × L(Gj ), Gi is contained
in GInit [xl ] and Gj is contained in GInit [xr ]. So GInit
displays the topology (ab, c) for the triplet of genes (a, b, c)
while GT R displays a different topology, either (a, bc) or
(ac, b). The assumption (*) is then impossible.
For example, in Figure 3, call x the white-colored node
of GInit . Then, | G(x) | = 3, and there does exist a node
y in GT R (the white-colored node) such that L(y) = L(x).
However, there exists no such node in G.

We denote by Vcons (GT R ) the subset of nodes y of
G
such that there exists a node x of GInit satisfying L(x) = L(y) and | G(y) | ≥ 2. For example, in
Figure 3, Vcons (GT R ) contains three nodes, the root, the
white-colored node and the lowest duplication node of
GT R . Lemma 6 allows to predetermine the sets of leaves
L(y) associated to the nodes y ∈ Vcons (GT R ). We now
describe how to find the best subtree GT R [y] for each
node y ∈ Vcons (GT R ), i.e. one leading to the minimum
reconciliation cost.
Note that if y ∈ Vcons (GT R ) and | G(y) | = 2, say
G(y) = {Gi , Gj }, 1 ≤ i < j ≤ k , then the M inSGT
algorithm can be applied to build the subtree GT R [y] as a
minimum reconciliation cost supergenetree for Gi and Gj .
It then remains to describe a recursive procedure for finding
the subtree GT R [y] for a node y ∈ Vcons (GT R ) such that
| G(y) | > 2.
In order to compute the reconciliation cost of the tree
GT R , we need to account for the local reconciliation costs
for the nodes y ∈ Vcons (GT R ), and also for the internal
nodes z of GT R such that z 6∈ Vcons (GT R ). To do so,
given a node y ∈ Vcons (GT R ), we define costT R (y) as
the local reconciliation cost for y , plus the local reconciliation costs for all internal nodes z ∈ V (GT R ) such that
z 6∈ Vcons (GT R ), y is an ancestor of z and there exists
no node y 0 ∈ Vcons (GT R ) on the path between y and z .
For example in Figure 3, call y the root of GT R . Then,
y ∈ Vcons (GT R ) and costT R (y) = cost(L(yl ), L(yr )) +
cost(L(yll ), L(ylr )) + cost(L(yrl ), L(yrr )) counting the local reconciliation costs for y , yl 6∈ Vcons (GT R ) and yr 6∈
Vcons (GT R ). We then obtain a formulation of the reconciliation cost of GT R as the sum of costT R (y) for all nodes
y ∈ Vcons (GT R ).
Lemma 7 describes the “valid” configurations of a subtree GT R [y] rooted at a node y ∈ Vcons (GT R ) such that
| G(y) | > 2, and the formula for computing costT R (y)
in each case. The following notations are used in Lemma
TR

7. Given a node x of GInit , and a node x∗ of GInit [xl ],
A(x∗ ) is the set of all strict ancestors of x∗ in GInit [xl ],
Al (x∗ ) is the subset of A(x∗ ) such that u ∈ Al (x∗ ) if
x∗ ∈ V (GInit [ul ]) and Ar (x∗ ) = A(x∗ ) \ Al (x∗ ).
Lemma 7. Let GT R be a triplet respecting supergenetree
for G = {G1 , . . . , Gk }. Let y be a node of GT R such that
y ∈ Vcons (GT R ) and | G(y) | > 2. Let x be the node of
GInit such that L(y) = L(x).
1)

2)
3)

If | G(xl ) | = 1 and | G(xr ) | ≥ 2, let
y ∗ ∈ Vcons (GT R ) be the node of GT R such that
L(y ∗ ) = L(xr ). The subtree GT R [y] can be obtained by taking the tree GInit [xl ] and grafting the
tree GT R [y ∗ ] onto it such that the root of GT R [y ∗ ]
appears as the sibling of a node x∗ of GInit [xl ].
The cost costT R (y) is then given by the following
formula:
costT R (y) = costT R (xl , xr , x∗ ) =
P
u ∈ Al (x∗ ) cost(L(ul ) ∪ L(xr ), L(ur ))
P
+ u ∈ Ar (x∗ ) cost(L(ul ), L(ur ) ∪ L(xr ))
P
+ u ∈ (V (GInit [xl ])\A(x∗ )) cost(L(ul ), L(ur ))
+cost(L(xl ), L(xr )) (if x∗ = xl )
If | G(xl ) | ≥ 2 and | G(xr ) | = 1, then this case
is symmetric to the previous case.
If | G(xl ) | ≥ 2 and | G(xr ) | ≥ 2, then GT R [y] is
such that L(yl ) = L(xl ) and L(yr ) = L(xr ), and
costT R (y) = cost(L(xl ), L(xr )).

Proof. In Case 1, we first deduce from Lemma 6 that there
must exist a node y ∗ ∈ Vcons (GT R ) such that L(y ∗ ) =
L(xr ). Next, GInit [xl ] is one of the gene trees of the set
G . So, it must be displayed by GT R [y] and then, GT R [y]
can be obtained by taking GInit [xl ] and grafting GT R [y ∗ ]
onto it. Finally, Case 2 is symmetric to Case 1 and Case 3
follows directly from Lemma 6. The formulas for costT R (y)
follows directly from the definition of costT R .
For example in Figure 3, the root and the white-colored
node of GT R fulfills the conditions of the first case. There
are no node y ∈ Vcons (GT R ) satisfying | G(y) | > 2 and
fulfilling the conditions of the second or third case.
We are now ready to describe the recurrence formula
of the recursive algorithm solving the M inT RS problem.
Given a node x of GInit such that | G(x) | ≥ 2, we denote
by M inT RS(GInit [x]) the minimum LCA-reconciliation
cost of a triplet respecting supergenetree compatible with
G(x).
Lemma 8. Let G = {G1 , . . . , Gk } be a setSof separated
k
subtrees of a gene tree GInit for Γ such that i=1 L(Gi ) =
Γ. Let x be a node of GInit such that | G(x) | ≥ 2.
1)
2)

(Stop condition) If | G(x) | = 2 (G(x) = {Gi , Gj }),
M inT RS(GInit [x]) = M inSGT (Gi , Gj ).
Otherwise (i.e | G(x) | > 2),
a)

If | G(xl ) | = 1 and | G(xr ) | ≥ 2,
M inT RS(GInit [x]) =
minx∗ ∈ V (GInit [xl ]) {costT R (xl , xr , x∗ )}
+M inT RS(GInit [xr ])

b)
c)

If | G(xl ) | ≥ 2 and | G(xr ) | = 1, this case
is symmetric to the previous case.
If | G(xl ) | ≥ 2 and | G(xr ) | ≥ 2,
M inT RS(GInit [x]) =
costT R (L(xl ), L(xr ))
+M inT RS(GInit [xl ])
+M inT RS(GInit [xr ])

Proof. The proof follows from Lemmas 6 and 7, and the fact
that each call to the recursive procedure M inT RS receives
as input a subtree GInit [x] such that | G(x) | ≥ 2, starting
with the whole tree rooted at r(GInit ). Case 1 is trivial. For
Case 2(a) (and symmetrically Case 2(b)), following Lemma
7, there are | V (GInit [xl ]) | possible configurations for the
subtree GT R [y] rooted at y = sGInit →GT R (x), depending
on which node x∗ of GInit [xl ] is chosen to be the sibling
of y ∗ = sGInit →GT R (xr ). Since GT R must be of minimum
reconciliation cost, the configuration for GT R [y] must be
one that locally minimizes the cost costT R (xl , xr , x∗ ). Finally, Case 3 follows directly from Lemma 7.
Complexity. we claim that Lemma 8 leads to a O(n2 )
algorithm for M inT RS , where n = |V (GInit )|. Let x be
a node of GInit , let nx be the number of nodes in GInit [x]
and let nl and nr be the number of nodes in the left and
right subtrees of x, respectively. As a base case, if x falls
into case 1 of Lemma 8, then running M inSGT on the two
child subtrees of x takes time O(max{nl , nr }2 ) = O(n2x ).
Suppose instead that x falls into case 2.a, and thus
G(xl ) = 1 and G(xr ) ≥ 2. We may assume by induction
that computing M inT RS(GInit [xr ]) requires time O(n2r ).
Afterwards, grafting the resulting tree is done on each
O(nl ) branch of GInit [xl ], and computing the cost can be
done in time O(nl ) for each grafting. Thus in total, case 2.a
can be handled in time O(n2r + n2l ) = O(n2x ). The case 2.b
of Lemma 8 is symmetric, and the case 2.c can be handled
in constant time. As the quadratic bound holds for every
node, we get a bound of O(n2x ) = O(n2 ) when x is the root.
Algorithm for M inLT RS . The algorithm for the M inT RS
problem can be adapted to solve the M inLT RS problem. The adaptation consists in (1) replacing the calls to
M inSGT (Gi , Gj ) in the stop condition of Lemma 8 by
calls to M inLSGT ((Gi , evi ), (Gj , evj )), and (2) replacing
the use of cost(Ll , Lr ) in order to define costT R (y) in
Lemma 7 by the use of costG (Ll , Lr ). Moreover, Lemma
5 must be extended such that costG (Ll , Lr ) = +∞ if
(Ll , Lr ) is not label-compatible with G . The complexity of
the algorithm remains unchanged in O(n2 ).

5. Experiments
In the context of gene tree correction, we wanted to
evaluate: (1) the benefit of the new supertree approach allowing to merge clades from different subtrees, compared with
the more constrained polytomy resolution approach [24]
which conserves input subtrees separated; (2) the benefit of
the additional triplet preservation requirement of M inT RS
and M inLT RS . Both evaluations were made based on the

M inSGT
M inLSGT
M inT RS
M inLT RS
P olytomySolver

% of
modified
trees
211
97.2%
207
95.3%
211
97.2%
207
95.3%
20 ms
9.2%

Avg.
running
time
205240 ms
113 ms
3031 ms
60 ms
3 ms

Avg
rec. cost
reduction
22.5
(24.8%)
19.5
(21.5%)
15.5
(17.1%)
13.5
(14.9%)
3.65
(4.0%)

Trees with
better
AU value

68.6%
66.4%
50.0%

TABLE 1. R ESULTS FOR THE 217 E NSEMBL TREES ( SEE TEXT FOR ALL DETAILS ). S ECOND COLUMN : NUMBER AND PERCENTAGE OF CORRECTED
TREES ; T HIRD COLUMN : MEAN RUNNING TIME FOR A TREE IN MS ; F OURTH COLUMN : MEAN VALUE AND PERCENTAGE OF THE RECONCILIATION
COST REDUCTION , I . E . DIFFERENCE IN RECONCILIATION COST BETWEEN THE ORIGINAL AND CORRECTED TREE ; L AST COLUMN : PERCENTAGE OF
CORRECTED TREES THAT HAVE A BETTER AU VALUE THAN THE ORIGINAL E NSEMBL TREES (D UE TO P HY ML’ S LONG COMPUTATION TIME , WE
COULD NOT OBTAIN THE AU VALUES FOR M inSGT AND M inLSGT ).

conjecture of dubious highest duplication nodes in gene
trees [17], [21].
For this purpose, we considered the gene trees of the
Ensembl vertebrate database Release 84 rooted at a duplication node. For each tree GInit , G was defined as the
set of all subtrees of GInit rooted at the “highest speciation nodes”, i.e. speciation nodes with only duplication
nodes as ancestors. On average, GInit contains 121.2 leaves
and is partitioned into 7.5 subtrees. Aiming at comparing
all developed algorithms, including the exponential time
M inSGT and M inLSGT , we restricted the sample to the
217 gene trees with at most 200 leaves and partitioned
into at most 5 subtrees. We also applied, on these 217
trees, P olytomySolver [24] which, given a set of trees
G1 , . . . , Gk , finds a binary tree with leafset {G1 , . . . , Gk }
such that the reconciliation cost of the resulting tree is
minimum. Results are given in Table 5.
While the four supertree algorithms correct more than
200 trees, corresponding to more than 95% of the 217 trees,
P olytomySolver only corrects 20 trees corresponding to
about 9% of the trees. Additionally, P olytomySolver reduces the reconciliation cost by only 4% on average on the
20 corrected trees, compared to more than 15% for supertree
algorithms. Clearly, by exploring a larger solution space,
M inSGT and M inLSGT allow to obtain the best solutions
in terms of reconciliation cost.
As for M inT RS and M inLT RS , although more constrained than M inSGT and M inLSGT , they lead surprisingly to almost as much correction as these two algorithms,
while the correction achieved by P olytomySolver is clearly
less. The triplet preserving constraint appears to be less
stringent than the conservation of the subtrees. In particular,
for the trees leading to only two subtrees, P olytomySolver
conserves the initial tree. Notice that introducing the labeling
constraint (M inSGT versus M inLSGT and M inT RS
versus M inLT RS ) only leads to a slight decrease of the
correction rates.
Finally, in order to assess the benefit of the triplet
respecting constraint and the quality of the correction
achieved, the trees corrected by M inT RS, M inLT RS and

P olytomySolver were evaluated according to their statistical support. PhyML [34] was executed to obtain the loglikelihood values per site (note that 150 trees were included
in this evaluation, as PhyML was very time-consuming on
the larger trees). Consel [35] was then run to evaluate, using
the AU (Approximately Unbiased) test, if the likelihood
differences of pairs of Ensembl and corrected gene trees
were significant enough to statistically reject one of them. A
tree can be rejected if its AU value, interpreted as a p-value,
is under 0.05. Otherwise, no significant evidence allows us
to reject one of the two trees.
Interestingly, when compared to the tree output by
M inT RS (respectively M inLT RS ), 48.5% (resp. 46.5%)
of the Ensembl gene trees are rejected compared to only
11.9% (resp. 11.0%) of the corrected gene trees. More than
68.6% (resp. 66.4%) of the corrected trees have better AU
values than original trees. As for PolytomySolver, 5% of the
Ensembl trees were rejected, as 25% of the corrected trees
were rejected, with 50% of the corrected trees obtaining
a better AU value. The performance of M inT RS and
M inLT RS is rather surprising as our correction, based
on the phylogenetic information of the species tree, is not
expected to improve tree likelihood based on sequence similarity. This may be an indication that high duplications are
actually dubious and that a correction specifically focusing
on such duplications is able to significantly improve the
accuracy of the tree. This observation is further supported
by the fact that the number of highest duplications is lower
for corrected trees than for initial trees (data not shown),
showing that our correction algorithms have the general
tendency of deleting high duplications.

6. Conclusion
This paper introduces a new methodology combining the
supertree and reconciliation frameworks with the purpose
of constructing a gene tree by combining a set of trees on
partial, possibly overlapping data. We also show how this
new paradigm is useful for gene tree correction. In particular, the artifact of duplications wrongly inferred close to the

root of a gene tree has been reported in the literature. Here,
we propose a new method for correcting a gene tree, by
first removing the higher duplication nodes and then finding
the supertree best fitting the species tree, that preserves the
remaining “trusted” subtrees, and possibly their hierarchical
position in the initial gene tree. This supertree approach
is shown to correct more trees than the approach based
on resolving a polytomy, as the first correction allows the
clustering of genes from different input subtrees. The corrected Ensembl gene trees are shown to exhibit less highest
duplication nodes and a lower reconciliation cost. Corrected
gene trees are also shown to have a better likelihood support.
This new gene tree construction and correction paradigm
leads to many new open problems. In particular, no proof
currently exists on the complexity of the problem of finding
a supergenetree minimizing the reconciliation cost, although
it is likely to be NP-hard, based on the fact that minimizing
the duplication cost is hard. The two problems (reconciliation versus duplication costs) probably also share the same
inapproximability properties. However, it is possible that
the supertree problems presented here are fixed-parameter
tractable with respect to parameters such as the number
of trees, the minimum reconciliation cost or the size of
the intersection between the leafset of the trees. This is an
area that deserves a more in-depth investigation. In addition,
while the extension to the labeled case has been done with
the same exponential complexity, adding the label restriction
strongly constrains the set of explored bipartitions, and we
can expect a more efficient algorithm in this case.
The problems we consider are build upon strong underlying assumptions, such as the consistency of input gene
trees, the compatibility and S -consistency of input gene
relations. A natural extension is then to integrate the notion
of a minimal correction of input trees to fit these preliminary
conditions. Finally, from an application point of view, rather
than removing higher duplication nodes, other types of gene
tree pruning can be envisaged and used to select the initial
“trusted” phylogenetic information that can then be combined using our supergenetree and reconciliation framework.

References
[1]

[2]
[3]
[4]

[5]

[6]
[7]

O. Bininda-Emonds, Ed., Phylogenetic Supertrees combining information to reveal The Tree Of Life, ser. Computational Biology.
Dordrecht, the Netherlands: Kluwer Academic, 2004.
M. Bansal, J. Burleigh, O. Eulenstein, and D. Fernández-Baca,
“Robinson-foulds supertrees,” Alg. Mol. Biol., vol. 5, no. 18, 2010.
N. Nguyen, S. Mirarab, and T. Warnow, “MRL and SuperFine+MRL:
new supertree methods,” Alg. Mol. Biol., vol. 7, no. 3, 2012.
V. Ranwez, V. Berry, A. Criscuolo, P. Fabre, S. Guillemot, C. Scornavacca, and E. Douzery, “PhySIC: a veto supertree method with
desirable properties,” Syst. Biol., vol. 56, no. 5, pp. 798- 817, 2007.
V. Ranwez, A. Criscuolo, and E. Douzery, “SuperTriplets: a tripletbased supertree approach to phylogenomics,” Bioinformatics, vol. 26,
no. 12, pp. i115- i123, 2010.
M. Steel and A. Rodrigo, “Maximum likelihood supertrees,” Syst.
Biol., vol. 57, no. 2, pp. 243- 250, 2008.
M. Swenson, R. Suri, C. Linder, and T. Warnow, “SuperFine: fast and
accurate supertree estimation,” Sys. Biol., vol. 61, no. 2, pp. 214-227,
2012, Special issue RECOMB-CG 2012.

[8]

M. Steel, “The complexity of reconstructing trees from qualitative
characters and subtrees,” J. Classif., vol. 9, pp. 91 - 116, 1992.

[9]

C. Scornavacca, L. van Iersel, S. Kelk, and D. Bryant, “The agreement
problem for unrooted phylogenetic trees is FPT,” J. Graph Algorithms
Appl., vol. 18, no. 3, pp. 385 - 392, 2014.

[10] A. Aho, S. Yehoshua, T. Szymanski, and J. Ullman, “Inferring a tree
from lowest common ancestors with an application to the optimization
of relational expressions,” SIAM J. Comput., vol. 10, no. 3, pp. 405421, 1981.
[11] M. Constantinescu and D. Sankoff, “An efficient algorithm for supertrees,” J. Classif., vol. 12, pp. 101- 112, 1995.
[12] M. Ng and N. Wormald, “Reconstruction of rooted trees from subtrees,” Discrete Appl. Math, vol. 69, pp. 19- 31, 1996.
[13] C. Semple, “Reconstructing minimal rooted trees,” Discrete Appl.
Math., vol. 127, no. 3, 2003.
[14] L. Li, C. J. Stoeckert, and D. Roos, “OrthoMCL: identification of
ortholog groups for eukaryotic genomes,” Genome Res., vol. 13, pp.
2178- 2189, 2003.
[15] A. Berglund, E. Sjolund, G. Ostlund, and E. Sonnhammer, “InParanoid 6: eukaryotic ortholog clusters with inparalogs,” Nucleic Acids
Res., vol. 36, pp. D263 - D266, 2008.
[16] M. Lechner, S. Findeib, L. Steiner, M. Marz1, P. Stadler, and
S. Prohaska, “Proteinortho: detection of (co-)orthologs in large-scale
analysis,” BMC Bioinformatics, vol. 12, p. 124, 2011.
[17] M. Hahn, “Bias in phylogenetic tree reconciliation methods: implications for vertebrate genome evolution,” Genome Biol., vol. 8, no.
R141, 2007.
[18] Y.-C. Wu, M. D. Rasmussen, M. S. Bansal, and M. Kellis, “TreeFix:
Statistically Informed Gene Tree Error Correction Using Species
Trees,” Syst. Biol., vol. 62, no. 1, pp. 110–120, 2013.
[19] K. Chen, D. Durand, and M. Farach-Colton, “Notung: Dating gene
duplications using gene family trees,” J. Computat. Biol., vol. 7, pp.
429–447, 2000.
[20] Y. Zheng and L. Zhang, “Reconciliation with non-binary gene trees
revisited,” in Proceedings of RECOMB 2014, ser. Lecture Notes Comput. Sci., vol. 8394, 2014, pp. 418-432, proceedings of RECOMB.
[21] K. M. Swenson and N. El-Mabrouk, “Gene trees and species trees:
Irreconcilable differences,” BMC Bioinformatics, vol. 13, no. (Suppl
19), p. S15, 2012.
[22] M. S. Bansal, Y. Wu, E. J. Alm, and M. Kellis, “Improved gene
tree error correction in the presence of horizontal gene transfer,”
Bioinformatics, vol. 31, no. 8, pp. 1211–1218, 2015.
[23] E. Noutahi, M. Semeria, M. Lafond, J. Seguin, B. Boussau,
L. Guguen, N. El-Mabrouk, and E. Tannier, “Efficient gene tree
correction guided by genome evolution,” Plos One, 2016, to appear.
[24] M. Lafond, E. Noutahi, and N. El-Mabrouk, “Efficient Non-Binary
Gene Tree Resolution with Weighted Reconciliation Cost,” in 27th
Annual Symposium on Combinatorial Pattern Matching (CPM 2016),
ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 54,
2016, pp. 14:1–14:12.
[25] S. Massey, A. Churbanov, S. Rastogi, and D. Liberles, “Characterizing
positive and negative selection and their phylogenetic effects,” Gene,
vol. 418, pp. 22- 26, 2008.
[26] M. Skovgaard, J. Kodra, D. Gram, S. Knudsen, D. Madsen, and
D. Liberles, “Using evolutionary information and ancestral sequences
to understand the sequence-function relationship in GLP-1 agonists,”
J. Mol. Biol., vol. 363, pp. 977- 988, 2006.
[27] S. Taylor, K. de la Cruz, M. Porter, and M. Whiting, “Characterization
of the long-wavelength opsin from Mecoptera and Siphonaptera: does
a flea see?” Mol. Biol. Evol., vol. 22, pp. 1165- 1174, 2005.
[28] M. Lafond, A. Ouangraoua, and N. El-Mabrouk, “Reconstructing a
supergenetree minimizing reconciliation,” BMC Genomics, vol. 16,
p. S4, 2015, Special issue of RECOMB-CG 2015.

[29] W. M. Fitch, “Homology. a personal view on some of the problems,”
Trends Genet., vol. 16, no. 5, pp. 227- 231, 2000.
[30] M. Lafond and N. El-Mabrouk, “Orthology and paralogy constraints:
satisfiability and consistency,” BMC Genomics, vol. 15, no. Suppl 6,
p. S12, 2014, Special issue RECOMB-CG 2014.
[31] L. Zhang, “On a Mirkin-Muchnik-Smith conjecture for comparing
molecular phylogenies,” J. Comput. Biol., vol. 4, no. 2, pp. 177- 187,
1997.
[32] C. Chauve and N. El-Mabrouk, “New perspectives on gene family
evolution: losses in reconciliation and a link with supertrees,” in
Proceedings of RECOMB 2009, ser. Lecture Notes Comput. Sci., vol.
5541. Springer, 2009, pp. 46-58.
[33] M. Hellmuth, M. Hernandez-Rosales, K. Huber, V. Moulton,
P. Stadler, and N. Wieseke, “Orthology relations, symbolic ultrametrics, and cographs,” J. Math. Biol., vol. 66, no. 1–2, pp. 399–420,
2013.
[34] S. Guindon and O. Gascuel, “A simple, fast, and accurate algorithm
to estimate large phylogenies by maximum likelihood,” Syst. Biol.,
vol. 52, no. 5, pp. 696–704, 2003.
[35] H. Shimodaira and M. Hasegawa, “CONSEL: for assessing the confidence of phylogenetoc tree selection,” Bioinformatics, vol. 17, pp.
1246- 1247, 2001.

