Biologically Feasible Gene Trees, Reconciliation Maps and Informative Triples
Marc Hellmuth









]Marc Hellmuth


[]Dpt. of Mathematics and Computer Science, University of Greifswald, Walther-
  Rathenau-Strasse 47, D-17487 Greifswald, Germany
 

	Saarland University, Center for Bioinformatics, Building E 2.1, P.O. Box 151150, D-66041 Saarbrücken, Germany
 Email: 




Biologically Feasible Gene Trees, Reconciliation Maps and Informative Triples
    [
     
=============================================================================



 

The history of gene families - which are equivalent to event-labeled gene trees - can be reconstructed from empirically  estimated evolutionary event-relations  containing pairs of orthologous, paralogous or xenologous genes.  The question then arises as whether inferred event-labeled gene trees are biologically feasible, that is, if there is a possible true history that would explain a given gene tree.  In practice, this problem is boiled down to finding a reconciliation map - also known as DTL-scenario - between the event-labeled gene trees and a (possibly unknown) species tree.  



In this contribution, we first characterize whether there is a valid
reconciliation map for binary event-labeled gene trees T that contain
speciation, duplication and horizontal gene transfer events and some unknown
species tree S in terms of “informative” triples that are displayed in T
and provide information of the topology of S. These informative triples are used to 
infer the unknown species tree S for T.
We obtain a similar result for non-binary gene trees. To this end, however, 
the reconciliation map needs to be further restricted. 
We provide a
polynomial-time algorithm to decide whether there is a species tree for a given
event-labeled gene tree, and in the positive case, to construct the
species tree and the respective (restricted) reconciliation map.


However, informative triples as well as DTL-scenarios have its limitations
when they are used to explain the biological feasibility of gene trees. 
While reconciliation maps imply biological feasibility, 
we show that the converse is not true in general.  Moreover, we show that 
informative triples do neither provide
enough information to characterize “relaxed” DTL-scenarios nor 
non-restricted reconciliation maps for 
non-binary biologically feasible gene trees.










§ BACKGROUND



The evolutionary history of genes is intimately linked with the history of the
species in which they reside. Genes are passed from generation to generation to
the offspring. Some of those genes are frequently duplicated, mutate, or get
lost - a mechanism that also ensures that new species can evolve. In particular,
genes that share a common origin (homologs) can be classified into the
type of their “evolutionary event relationship”, namely orthologs, paralogs
and xenologs <cit.>. Two homologous genes are
orthologous if at their most recent point of origin the ancestral gene is
transmitted to two daughter lineages; a speciation event happened. They
are paralogous if the ancestor gene at their most recent point of origin
was duplicated within a single ancestral genome; a duplication event
happened. Horizontal gene transfer (HGT) refers to the transfer of genes between
organisms in a manner other than traditional reproduction and across different
species and yield so-called xenologs.
In contrast to orthology and paralogy, the definition of xenology is less
well established and by no means consistent in the biological
literature. One definition stipulates that two genes are
xenologs if their history since their common ancestor involves
horizontal transfer of at least one of them <cit.>. 
The mathematical framework for evolutionary event-relations 
relations in terms of symbolic
ultrametrics, cographs and 2-structures <cit.>, on the other hand, naturally
accommodates more than two types of events associated with the internal nodes of
the gene tree. We follow the notion in 
<cit.> and call two genes xenologous,  whenever 
their least common ancestor was a HGT event.  

The knowledge of evolutionary event relations such as orthology, paralogy or
xenology is of fundamental importance in many fields of mathematical and
computational biology, including the reconstruction of evolutionary
relationships across species <cit.>,
as well as functional genomics and gene organization in species
<cit.>. Intriguingly, there are methods to infer orthologs
<cit.>
or to detect HGT <cit.> without
the need to construct gene or species trees. Given  empirical estimated
event-relations one can infer the history of gene families which are
equivalent to event-labeled gene trees <cit.>. For an
event-labeled gene tree to be biologically feasible there must be a putative
“true” history that can explain the observed gene tree. However, in practice
it is not possible to observe the entire evolutionary history as e.g. gene
losses eradicate the entire information on parts of the history. Therefore, in
practice the problem of determining whether an event-labeled gene tree is
biologically feasible is reduced to the problem of finding a valid
reconciliation map, also known as DTL-scenario, between the event-labeled gene
trees and an arbitrary (possibly unknown) species tree. Tree-reconciliation
methods have been extensively studied over the last years
<cit.>
and are often employed to identify inner vertices of the gene tree as a
duplication, speciation or HGT, given that both, the gene and the species tree
are available.

In this contribution, we assume that only the event-labeled gene tree T is available and wish
to answer the question: How much information about the species tree S and the 
reconciliation  between T and S is already contained in the gene tree T?
As we shall see, this question can easily be answered for binary gene trees in terms
of “informative” triples that are displayed in T and provide
information on the topology of S. The latter generalizes results established
by Hernandez et al. <cit.> for the HGT-free case. 
To obtain a similar result for non-binary gene trees, we show
that the reconciliation map needs to be restricted. 
Nevertheless, informative triples can then  be used to characterize whether
there is a valid restricted reconciliation map for a given non-binary
gene tree and some unknown species tree S, as well as to construct S,
provided the informative triples are consistent. 
However, this approach
has also some limitations. We prove that 
“informative” triples are not sufficient to characterize the existence
of  a possibly “relaxed” reconciliation map.
Moreover, while reconciliation maps give clear evidence of gene trees to be biologically feasible, 
the converse is in general not true. We provide a simple example that shows that not all
biologically feasible gene trees can be explained by DTL-scenarios. 




§ PRELIMINARIES





A rooted tree T=(V,E) (on L) is an acyclic connected simple graph
with leaf set L⊆ V, set of edges E, and set of interior vertices
V^0=V∖ L such that there is one distinguished vertex ρ_T ∈ V,
called the root of T. 



A vertex v∈ V is called a descendant of u∈ V, v ≼_T u, and u is an
ancestor of v, u ≽_T v, if u lies on the path from
ρ_T to v. As usual, we write v ≺_T u and u ≻_T v to
mean v ≼_T u and u v.  
If u ≼_T v or v ≼_T u then u and v
are comparable and otherwise, incomparable.  
For x∈ V, we write L_T(x):={ y∈ L| y≼ x} for the
set of leaves in the subtree T(x) of T rooted in x. 



It will be convenient to use a notation for edges e that implies which of the vertex in
e is closer to the root. Thus, the notation for edges (u,v) of a tree
is always chosen such that u≻_T v. 


For our discussion below we need to extend the ancestor relation ≼_T on
V to the union of the edge and vertex sets of T. More precisely, for the
edge e=(u,v)∈ E we put x ≺_T e if and only if x≼_T v and e
≺_T x if and only if u≼_T x. For edges e=(u,v) and f=(a,b) in
T we put e≼_T f if and only if v ≼_T b. In the latter case, 
the edges e and f are called comparable.

For a non-empty subset of leaves A⊆ L, we define _T(A), or the
least common ancestor of A, to be the unique ≼_T-minimal vertex
of T that is an ancestor of every vertex in A. In case A={x,y }, we put
_T(x,y):=_T({x,y}) and if A={x,y,z }, we put
_T(x,y,z):=_T({x,y,z}). For later reference, note that for all x∈
V it hold that x=_T(L_T(x)). We will also make frequent use that for two
non-empty vertex sets A,B of a tree, it always holds that (A∪ B) =
((A),(B)). 






A phylogenetic tree T (on L) is a rooted tree T=(V,E) (on L) such
that no interior vertex  v∈ V^0 has degree two, except possibly the root 
ρ_T. If L corresponds to a set of genes 
or species , we call a phylogenetic tree on L gene tree
and species tree, respectively. The restriction T|_L' of of a
phylogenetic tree T to L'⊆ L is the rooted tree with leaf set L'
obtained from T by first forming the minimal spanning tree in T with leaf
set L' and then by suppressing all vertices of degree two with the exception
of ρ_T if ρ_T is a vertex of that tree.
	



Rooted triples are phylogenetic trees on three leaves with precisely two
interior vertices. They constitute an important concept in the context of
supertree reconstruction <cit.> and will
also play a major role here. A rooted tree T on L displays a triple
xy|z if, x,y,z∈ L and the path from x to y does not intersect the
path from z to the root ρ_T and thus, having _T(x,y)≺_T
_T(x,y,z). We denote by R(T) the set of all triples that are
displayed by the rooted tree T.  

A set R of triples is consistent if there is a rooted tree T on L_R=
∪_r∈ R L_r(ρ_r) such that R⊆R(T) and thus, T
displays each triple in R. Not all sets of triples are consistent of
course. Nevertheless, given a triple set R there is a polynomial-time
algorithm, referred to in <cit.> as , that
either constructs a phylogenetic tree T that displays R or that recognizes
that R is not consistent <cit.>. 
The runtime of BUILD is O(|L_R||R|) <cit.>. 
Further practical implementations and improvements have been
 discussed in  <cit.>.


We will consider rooted trees
T=(V,E) from which particular edges are removed. Let ⊆ E and
consider the forest (V,E∖). We can preserve the
order ≼_T for all vertices within one connected component of  and
define ≼_ as follows: x≼_y iff x≼_Ty and
x,y are in same connected component of . Since each connected component
T' of  is a tree, the ordering ≼_ also implies a root
ρ_T' for each T', that is, x≼_ρ_T' for all x∈
V(T'). If L() is the leaf set of , we define L_(x) = {y∈
L() | y≺_ x} as the set of leaves in  that are reachable
from x. Hence, all y∈ L_(x) must be contained in the same connected
component of . We say that the forest  displays a triple r, if r
is displayed by one of its connected components. Moreover, R() denotes
the set of all triples that are displayed by the forest .  





§ BIOLOGICALLY FEASIBLE AND OBSERVABLE GENE TREES



A gene tree  arises through a series of events (speciation, duplication, HGT,
and gene loss) along a species tree. In a “true history” the gene tree
T = (V,E) on a set of genes  is equipped with an 
event-labeling map t:V∪ E→ I∪{0,1} with
I={,,,⊙,x} that assigns to each
vertex v of T a value t(v)∈ I indicating whether v is 
a speciation event (), duplication event (), HGT event
(), extant leaf (⊙) or a loss event (x).
In addition, to each edge e a value t(e)∈{0,1} is added that
indicates whether e is a transfer edge (1) or not (0).
Note, in the figures we used the symbols ∙, □ and 
for , and  respectively.
Hence, e=(x,y) and t(e) =1 iff t(x)= and the genetic material is
transferred from the species containing x to the species containing y. 
We remark that the restriction t_|V of t to the vertex set V was introduced
as “symbolic dating map” in <cit.> and that there is a close
relationship to so-called cographs <cit.>.
Let ⊆ be the set of all extant genes in T. 
Hence,  there is a map σ:→ that assigns to each extant gene the extant species in which it resides. 


We assume that the gene tree and its event labels are inferred from
(sequence) data, i.e., T is restricted to those labeled trees that can be
constructed at least in principle from observable data. 
Gene losses eradicate the entire information on parts of the history and thus, 
cannot directly be observed from extant sequences.  
Hence, in our setting the (observable) gene tree T is the restriction  T_| to
the set of extant genes, see Figure <ref>.
Since all leaves of T are extant genes in  we don't need to specially
label the leaves in , and thus simplify the 
event-labeling map t:V^0∪ E→ I∪{0,1} by assigning only to the 
interior vertex an event in I={,,}. 
We assume here that all non-transfer edges transmit the genetic material vertically, 
that is, from an ancestral species to its descendants.



We write (T;t,σ) for the  tree T=(V,E) with event-labeling t
and corresponding map σ. The set = {e∈ E| t(e)=1} 
will always denote  the set of transfer edges in  (T;t,σ). 

Additionally, we consider gene tree (T=(V,E);t,σ) from which the transfer edges have been removed, resulting
in the forest = (V, E∖) in which we preserve the event-labeling t,
that is, we use the restriction t_|V on . 


We call a gene tree (T;t,σ) on  biologically feasible, 
if there is a true scenario such that T = T_|, that is, 
there is a true history that can explain  (T;t,σ). 
By way of example, the gene tree in Figure <ref>(right) 
is biologically feasibly. 
However, so-far it is unknown whether there are gene trees (T;t,σ)
that are not biologically feasible. 
Answering the latter might be a hard task, as many HGT or duplication vertices 
followed by losses can be inserted into T that may result in a putative
true history that explains the event-labeled gene tree.





Following Nøjgaard et al. <cit.>, we additionally restrict the set of observable gene trees (T;t,σ) 
to those gene trees that satisfy the following observability axioms:



  (O1) Every internal vertex v has degree at least 3, except
  possibly the root which has degree at least 2. 

  (O2) Every HGT node has at least one transfer edge, t(e)=1, and at
  least one non-transfer edge, t(e)=0; 

  (O3) (a) 
If x∈ V is a speciation vertex, 
then there are distinct children v,
w of x in T with 
	(v)∩(w) = ∅. 

(b) 
If (x,y) ∈, then 
	(x)∩(y) = ∅.
 







 Condition (O1) is justified by the restriction T=T_| 
of the true binary gene tree T to the set of extant genes , 
since  T=T_| is always a phylogenetic tree. 
In particular, (O1) ensures that every event leaves a historical trace in the
sense that there are at least two children that have survived in at least
two of its subtrees. 
Condition (O2) ensures that for
an HGT event a historical trace remains of both the transferred and the
non-transferred copy.  

Condition (O3.a) is a consequence of (O1), (O2) and a stronger condition (O3.a') claimed in <cit.>:
If x is a speciation vertex, then there
are at least two distinct children v,w of x such that the species V
and W that contain v and w, resp., are incomparable in S.
Note, a speciation vertex x cannot be observed from data
if it does not “separate” lineages, that is, there are two leaf
descendants of distinct children of x that are in distinct
species. Condition (O3.a') is even weaker and 
ensures that any “observable” speciation vertex x separates at
least locally two lineages. As a result of  (O3.a') one can obtain
(O3.a) <cit.>.
Intuitively, (O3.a) is satisfied since within a connected component of  no
genetic material is exchanged between non-comparable nodes. Thus, a gene
separated in a speciation event necessarily ends up in distinct species in
the absence of the transfer edges. 


Condition (O3.b) is a consequence of (O1), (O2) and a stronger condition (O3.b') claimed in <cit.>:
If (v,w) is a transfer edge in T, then   t(v)= and the
species V and W that contain v and w, resp., are
incomparable in S.
Note, if (v,w)∈ then v signifies the transfer event
itself but w refers to the next (visible) event in the gene tree
T.  In a “true
history” v is contained in a species V that transmits its genetic
material (maybe along a path of transfers) to a contemporary species Z
that is an ancestor of the species W containing w. In order to have
evidence that this transfer happened, Condition (O3.b') is used and
as a result one obtains (O3.b). 
The intuition behind  (O3.b) is as follows:
Observe that  (x) and (y) are subtrees of distinct connected
components of  whenever (x,y) ∈. 
Since HGT amounts to the transfer of genetic material
across distinct species, the genes x and y are in distinct
species, cf. (O3.b). However, since  does not contain transfer edges  and thus, there is no
genetic material transferred across distinct species between distinct
connected components in . We refer to <cit.> for further details



In what follows, we only consider  gene trees (T;t,σ)
that satisfy (O1), (O2) and (O3).

We simplify the notation a bit and write (u):=σ(L_(u)).



Based on Axiom (O2) the following results was established in <cit.>.

Let (T;t,σ) be an event-labeled gene tree.








	

Let 𝒯_1, …, 𝒯_k be
the connected components of  with roots ρ_1, …, ρ_k,
respectively. 
Then, {L_(ρ_1), …, L_(ρ_k)} forms a partition of . 






Lemma  <ref> particularly implies that 
(x) ≠∅ for all x∈ V(T). Note, 
 might contain interior vertices (distinct from the root)
that have degree two. Nevertheless, for each x≼_ y in
 we have x≼_T y in T. Hence, partial information (that in
particular is “undisturbed” by transfer edges) on the partial ordering of the
vertices in T can be inferred from .




§ RECONCILIATION MAP


Before we define a reconciliation map that “embeds” a
given gene tree into a given species tree we need a slight modification 
of the species tree.
In order to account for duplication events
that occurred before the first speciation event, we need to add an extra vertex
and an extra edge “above” the last common ancestor of all species: hence, we
add an additional vertex to W (that is know the new root ρ_S of S) and the
additional edge (ρ_S,_S())∈ F. Note that strictly speaking S is
not a phylogenetic tree anymore. In case there is no danger of confusion, we
will from now on refer to a phylogenetic tree on  with this extra edge and
vertex added as a species tree on .


  
  Suppose that  is a set of species, S=(W,F) is a phylogenetic tree on
  , T=(V,E) is a gene tree with leaf set  and that σ:→ and t:V^0→{,,}∪{0,1} are the
  maps described above. Then we say that S is a species tree for
  (T;t,σ) if there is a map μ:V→ W∪ F such that, for all x∈
  V:  


  (M1) Leaf Constraint.  If x∈   then μ(x)=σ(x). 		


  (M2) Event Constraint.
	
		
  (i)  If t(x)=, then  
                  μ(x) = _S((x)).
		
  (ii) If t(x) ∈{, }, then μ(x)∈ F. 
		
  (iii) If t(x)= and (x,y)∈, 
						 then μ(x) and μ(y) are incomparable in S. 
 	 


  (M3) Ancestor Constraint.		
	
		Let x,y∈ V with x≺_ y. 
		Note, the latter implies that the path connecting x and y in T
		does not contain transfer edges.
		We distinguish two cases:
	
		
  (i) If t(x),t(y)∈{, }, then μ(x)≼_S μ(y), 
		
  (ii) otherwise, i.e., at least one of t(x) and t(y) is a speciation , 
						μ(x)≺_Sμ(y).
	

We call μ the reconciliation map from (T;t,σ) to S. 
                

Definition <ref> is a natural generalization of the map defined in
<cit.>, that is, in the absence of horizontal gene transfer, Condition
(M2.iii) vanishes and thus, the proposed reconciliation map precisely coincides
with the one given in <cit.>.
In case that the event-labeling of T is unknown, but a species tree S is
given, the authors in <cit.> gave an axiom set, called
DTL-scenario, to reconcile T with S. This reconciliation is then used to
infer the event-labeling t of T. 
The “usual” DTL axioms explicitly refer to binary,
fully resolved gene and species trees. We therefore use a different axiom set
that is, nevertheless, equivalent to DTL-scenarios
in case the considered gene trees are binary <cit.>.



Condition (M1) ensures that each leaf of T, i.e., an extant gene in , is
mapped to the species in which it resides. 
Condition (M2.i) and (M2.ii) ensure
that each vertex of T is either mapped to a vertex or an edge in S such that
a vertex of T is mapped to an interior vertex of S if and only if it is a
speciation vertex. We will discuss (M2.i) in further detail below. 
Condition (M2.iii) maps the vertices of a transfer edge
in a way that they are incomparable in the species tree and is used
to satisfy axiom (O3). 
Condition (M3) refers only to the connected components of  and
is used to preserve the ancestor order ≼_T of T along the paths
that do not contain transfer edges is preserved. 

It needs to be discussed, why one should map a speciation vertex x to 
_S((x)) as required in (M2.i). The next lemma shows, that one
can put μ(x) = _S((x)).  

	Let μ be a reconciliation map  from (T;t,σ) to S
	that satisfies (M1) and (M3), then
   μ(u)≽_S _S((u)) for any u∈ V(T). 


Condition (M2.i) implies in particular the weaker property “(M2.i') if
t(x)= then μ(x)∈ W”. In the light of
Lemma <ref>, μ(x)=_S((x)) is the lowest possible
choice for the image of a speciation vertex. 
Instead of considering the
possibly exponentially many reconciliation maps for which
μ(x)≻_S_S((x)) for speciation vertices x is allowed
we restrict our attention to those that satisfy (M2.i) only. 
In particular, as we shall see later, there is a neat characterization
of maps that satisfy (M2.i) that does, however, 
not work for maps with “relaxed” (M2.i). 

Moreover, we have the following result, which is a mild
generalization of <cit.>. 

	Let μ be a reconciliation map from a gene tree (T;t,σ) to S. 
	
		
		
  * If v,w∈ V(T) are in the same connected component of ,   then 
					μ(_(v,w)) ≽_S _S(μ(v),μ(w)).
					



		
  * If (T;t,σ) is a binary gene tree and x a speciation vertex with children v,w in T, then  
				   then μ(v) and μ(w) are incomparable in S.  
		








	Let v,w∈ V(T) be in the same connected component of . 
	Assume that v and w are comparable in  and 
	that w.l.o.g. v≻_ w. Condition (M3) implies that 
	μ(v)≽_Sμ(w). Hence, 
	v = _(v,w) and 
	μ(v) = _S(μ(v),μ(w)) and we are done. 

	Now assume that  v and w are incomparable in . 
	Consider the unique path P connecting w with v in . This path P
	is uniquely subdivided into a path P' and a path P” from
	_(v,w) to v and w, respectively. Condition (M3) implies that
	the images of the vertices of P' and P” under μ, resp., are ordered
	in S with regards to ≼_S and hence, are contained in the intervals
	Q' and Q” that connect μ(_(v,w)) with μ(v) and
	μ(w), respectively. In particular, μ(_(v,w)) is the largest
	element (w.r.t. ≼_S) in the union of Q'∪ Q” which contains the
	unique path from μ(v) to μ(w) and hence also _S(μ(v),μ(w)).
		
	Item <ref> was already proven in <cit.>.




Assume now that there is a reconciliation map μ from (T;t,σ) to S. 
From a biological point of view, however, it is necessary to reconcile a gene
tree with a species tree such that genes do not “travel through time”, a
particular issue that must be considered whenever (T;t,σ)  contains HGT, 
see Figure <ref> for an example. 


  The map : V(T) →ℝ is a time map for the 
  rooted tree T if x≺_T y implies (x)>(y) for all 
  x,y∈ V(T). 


  A reconciliation map μ from
  (T;t,σ) to S is time-consistent if there are time maps
  τ_T for T and τ_S for S for all u∈ V(T) satisfying the
  following conditions:
  
  
  (T1) If t(u) ∈{, ⊙}, then 
    τ_T(u) = τ_S(μ(u)). 
  
  (T2) If t(u)∈{,} and, thus
    μ(u)=(x,y)∈ E(S),  then
    τ_S(y)>τ_T(u)>τ_S(x). 

 

Condition (T1) is used to identify the time-points of speciation vertices 
and leaves u in the gene tree with the time-points of their respective 
images μ(u) in the species trees. Moreover, 
duplication or HGT vertices u are mapped to edges μ(u)=(x,y) in S
and the time point of u must thus lie between the time
points of x and y which is ensured by Condition (T2).
Nøjgaard et al. <cit.> designed an O(|V(T)|log(|V(S)|))-time algorithm 
to check whether a given reconciliation map μ is time-consistent, and an algorithm with the same
time complexity for the construction of a time-consistent reconciliation
map, provided one exists.
Clearly, a necessary condition for the existence of time-consistent reconciliation maps from 
(T;t,σ) to S is the  existence of some reconciliation map 
(T;t,σ) to S. 
In the next section,  we first characterize the existence of reconciliation maps
and discuss open  time-consistency problems. 







§ FROM GENE TREES TO SPECIES TREES



Since a gene tree T is uniquely determined by its induced triple set
ℛ(T), it is reasonable to expect that a lot of information on the
species tree(s) for (T;t, σ) is contained in the images of the triples in
ℛ(T), (or more precisely their leaves) under σ. However, not
all triples in ℛ(T) are informative, see Figure <ref> for
an illustrative example. In the absence of HGT, it has already been shown by
Hernandez-Rosales et al. <cit.> that the informative triples r∈ℛ(T) are precisely those that are rooted at a speciation event and
where the genes in r reside in three distinct species. However, in the
presence of HGT we need to further subdivide the informative triples as follows.




  
	Let (T;t,σ) be a given event-labeled gene tree with respective
	set of transfer-edges = {e_1,…,e_h}  and 	as defined above. 
	We define 
	
    () = {ab|c∈R()    σ(a),σ(b),σ(c) 
       are pairwise distinct}

	as the subset of all triples displayed in  such that the leaves are from pairwise distinct species.	

	Let
	
    R_0() {ab|c∈()   t(_(a,b,c)) = }

	be the set of triples in  () that are rooted at a speciation event.

	For each e_i=(x,y) ∈ define 
	
    R_i()	{ab|c   σ(a),σ(b),σ(c)   are pairwise distinct
       and either   a,b∈ L_(x), c∈ L_(y) 
       or  c∈ L_(x), a,b∈ L_(y)  }.
	
	Hence, R_i() contains a triple ab|c for every 
	a,b∈ L_(x), c∈ L_(y) that reside in pairwise distinct species. Analogously,  for any a,b∈ L_(y), c∈ L_(x) there is a triple ab|c∈R_i(), if
	σ(a),σ(b),σ(c) are pairwise distinct. 

	The informative triples of T are comprised in the set 	
	ℛ(T;t,σ) = ∪_i=0^h R_i().


	Finally, we define the informative species triple set 
	
    𝒮(T;t,σ){σ(a)σ(b)|σ(c)ab|c∈ℛ(T;t,σ) }

	that can be inferred from the informative triples of (T;t,σ).
                









 §.§ Binary Gene Trees







In this section, we will be concerned
only with binary, i.e., “fully resolved” gene trees,
if not stated differently. 
This is justified by
the fact that, generically, a speciation or duplication event
instantaneously generates exactly two offspring. However, we will allow
also non-binary species tree to model incomplete knowledge of the exact
species phylogeny. Non-binary gene trees are discussed in Section <ref>.

Hernandez et al.  <cit.> established the following characterization for the HGT-free case. 

	For a given gene tree (T;t, σ) on  that does not contain
	HGT and 𝔖{σ(a)σ(b)|σ(c)ab|c∈ℛ_0(T)}, the following statement is satisfied:
		
	There is a species tree on = σ() for (T;t, σ)
	 if	and only if the triple set 𝔖 is consistent.


We emphasize that the results established in <cit.> are only valid
for binary gene trees, although this was not explicitly stated.
For an example that shows that Theorem <ref> 
does is no always satisfied for non-binary gene trees see 
Figure <ref>. 
Lafond and El-Mabrouk <cit.> established
a similar result as in Theorem <ref> by using
only species triples that can be obtained directly
from a given orthology/paralogy-relation. However, they require a stronger
version of axiom (O3.a), that is, the images of all children of a
speciation vertex must be pairwisely incomparable in the species tree. 
We, too, will use this restriction in Section <ref>

In what follows, we generalize the latter result and show that consistency of
𝒮(T;t,σ) characterizes whether there is a species tree S for
(T;t,σ) even if (T;t,σ) contains HGT. 






	If μ is a reconciliation map from a gene tree (T;t,σ) to 
	a species tree S
	and ab|c∈ℛ(T;t,σ), then 
	σ(a)σ(b)|σ(c) is displayed in S.
  


	Recall that  is the leaf set of T=(V,E) and, by Lemma <ref>, 
	of . 	


	Let {a,b,c}∈3 and assume w.l.o.g. ab|c∈ℛ(T;t,σ).

	First assume that ab|c∈R_0, that is ab|c is displayed
	in  and t(_(a,b,c)) =. For simplicity set
	u=_(a,b,c) and let x,y be its children in . 
	Since ab|c∈R_0, we can assume that w.l.o.g. 
	a,b∈ L_(x) and c∈ L_(y). 	
	Hence,  x≽__(a,b) and y≽_ c. 
   Condition (M3) implies that
	μ(y)≽_S μ(c) = σ(c). Moreover, Condition (M3) and Lemma
	<ref>(<ref>) imply that μ(x)≽_S
	μ(_(a,b)) ≽_S _S(μ(a),μ(b)) =
	_S(σ(a),σ(b)). 
Since t(u)=, we can apply 	Lemma <ref>(<ref>) 
	and conclude that μ(x) and μ(y) are incomparable in S. Hence,
	σ(c) and _S(σ(a),σ(b)) are incomparable. Thus, the
	triple σ(a)σ(b)|σ(c) must be displayed in S.






































	Now assume that ab|c∈R_i for some transfer edge e_i = (x,y)∈. 
	For e_i = (x,y) we either have a,b∈ L_(x) and c∈ L_(y) or c∈
	L_(x) and a,b∈ L_(y). W.l.o.g. let 
	 a,b∈ L_(x) and c∈ L_(y). Thus, x≽__(a,b) and y≽_ c. Condition (M3) implies that
	μ(y)≽_S μ(c) = σ(c). Moreover, Condition (M3) and Lemma
	<ref>(<ref>) imply that μ(x)≽_S
	μ(_(a,b)) ≽_S _S(μ(a),μ(b)) =
	_S(σ(a),σ(b)). Since t(x)=, we can apply (M2.iii)
	and conclude that μ(x) and μ(y) are incomparable in S. Hence,
	σ(c) and _S(σ(a),σ(b)) are incomparable. Thus, the
	triple σ(a)σ(b)|σ(c) must be displayed in S.


	




	
	Let S=(W,F) be a species tree on . 
	Then there is reconciliation map 	μ  from a  gene tree (T;t,σ) to S
	whenever S displays all triples in 𝒮(T;t,σ).



	Recall that  is the leaf set of T=(V,E) and, by Lemma <ref>, of . In what follows, we write (u) instead of
	the more complicated writing L_(u) and, for consistency and simplicity, 
	we also often write σ((u)) instead of (u). 
	Put S=(W,F) and 𝒮 =
	𝒮(T;t,σ). We first consider the subset U={x∈ V | x∈ or  t(x) =  }}  
   of V comprising the leaves and speciation
	vertices of T.

	In what follows we will explicitly construct μ: V → W∪ F
	and verify that μ satisfies Conditions (M1), (M2) and (M3). 
	To this end, we first set for all x∈ U:
	
		
  (S1) μ(x) = σ(x), if x∈,
		
  (S2) μ(x)= _S(σ((x))), if t(x)=.
	
	Conditions (S1) and (M1), as well as (S2) and (M2.i) are equivalent. 
	
	For later reference, we show that _S(σ((x))) ∈ W^0 =
	W∖ and that there are two leaves a,b∈(x) such that 
	 σ(a) ≠σ(b),  whenever t(x)=.

	Condition (O3.a) implies that
	x has  two children v and
	w in T such that  σ((v)) ∩σ((w)) = ∅. Moreover, 
	Lemma <ref> implies that both (v) and (w) are
	non-empty subsets of  and hence, neither 
	σ((v))=∅ nor 	σ((w))=∅.





	Thus, there are two leaves a, b∈(x) such
	that σ(a) ≠σ(b). Hence, _S(σ((x))) ∈ W^0 =
	W∖. 



	
	
  * Claim 1: For all x,y∈ U with x≺_ y we have μ(x)≺_S μ(y).

	Note, y must be an interior vertex, since x≺_ y. Hence t(y)=.
	
	If x is a leaf, then μ(x)=σ(x)∈. As argued above, 
	μ(y) ∈ W∖. Since x∈(y) and 
	σ((y))≠∅, 
	
	 we have 
	σ(x) ∈σ((y))⊆ and thus, μ(x)≺_S μ(y). 

	Now assume that x is an interior vertex and hence, t(x)=.
	Again, there are leaves a,b ∈(x) with 
	A = σ(a)≠σ(b)=B.

	Since t(y)=, vertex y has two children in . Let y' denote the child of  
	y with	x≼_ y'. 
	Since (x)⊆(y')⊊(y),
	we have (y)∖(y')≠∅ and, by 
	Condition (O3.a), 
	there is a gene c∈(y)∖(y') ⊆(y)∖(x) with
	σ(c)=C≠ A,B. 
	By construction, ab|c∈R_0 and hence,
	AB|C∈𝒮(T;t,σ).







	Hence, _S(A,B)≺_S _S(A,B,C). 
	Since this holds for all triples x'x”|z with x',x”∈(x)
	and z∈(y)∖(y'), 
	
	we can conclude that 
	
    μ(x)    = _S(σ((x)))  
       ≺_S        
    				 _S(σ((x))∪σ((y) ∖(y'))).



	Since σ((x))∪σ((y) ∖(y')) ⊆σ((y))
   we obtain 
	
    _S(σ((x))∪σ((y) ∖(y'))) 
       ≼_S  
    					_S(σ((y))) = μ(y).

	Hence,  μ(x)≺_Sμ(y).





	_– End Proof Claim 1 –
		

	We continue to extend μ to the entire set V. To this end, observe first
	that if t(x) ∈{, } then we wish to map x on an edge
	μ(x) = (u,v) ∈ F such that Lemma <ref>
	is satisfied: v≽_S _S(σ((x))). Such an edge exists for v
	= _S(σ((x))) in S by construction. Every speciation vertex y
	with y≻_ x therefore necessarily maps on the vertex u or above,
	i.e., μ(y) ≽_S u must hold.
	Thus, we set:
	
		
  (S3) μ(x) = (u,_S(σ((x)))), if t(x)∈{, },
	
	which now makes μ a map from V to W∪ F.	

	By construction of μ, Conditions (M1), (M2.i), (M2.ii) are satisfied by μ. 

	We proceed to show that (M3) is satisfied.

	
	
  * Claim 2: 
	 For all x,y∈ V with x≺_ y, Condition (M3) is satisfied.
 
	If both x and y are speciation vertices, then we can apply the Claim 1
	to conclude that μ(x)≺_S μ(y).
	If x is a leaf, then we argue similarly as in the proof of Claim 1
	to conclude that μ(x)≼_S μ(y).

	Now assume that both x and y are interior vertices of T and 
	at least one vertex of x,y is not a speciation vertex.
	Since, x≺_ y we have (x) ⊆(y) and thus,  σ((x)) ⊆σ((y)).

	We start with the case t(y)= and t(x)∈{, }.
	Since t(y)=, vertex y has two children in . Let y' be the child of y with
   x≼_ y'. 
	If σ((x)) contains only one species A, then
	μ(x) = (u,A)≺_S u≼_S _S(σ((y))) = μ(y).
	If σ((x)) contains at least two species, then there are a,b∈(x) with σ(a)=A≠σ(b)=B
	Moreover, since (x)⊆(y')⊊(y),
	we have (y)∖(y')≠∅ and, by 
	Condition (O3.a), 
	there is a gene c∈(y)∖(y') ⊆(y)∖(x) with
	σ(c)=C≠ A,B. 
	By construction, ab|c∈R_0 and hence
	AB|C∈𝒮(T;t,σ). Now we can argue similar as in the proof of the
	Claim 1, to see that 


	 
    μ(x)    = (u,_S(σ((x)))) ≺_S u 
       ≼_S
    	_S(σ((y))) = μ(y).


	If t(x)= and t(y)∈{, }, then σ((x))
	⊆σ((y)) implies that 


	 
    μ(x)    =	_S(σ((x)))≼_S _S(σ((y))) 
       ≺_S(u,_S(σ((y)))) = μ(y).


	Finally assume that t(x),t(y)∈{, }. If σ((x))
	= σ((y)), then μ(x) = μ(y). Now let σ((x)) ⊊σ((y)) which implies that _S(σ((x)))≼_S
	_S(σ((y))). If _S(σ((x))) =
	_S(σ((y))), then μ(x) = μ(y). If
	_S(σ((x)))≺_S _S(σ((y))), 
	then 



	 
    μ(x)   =(u,_S(σ((x)))) ≺_S u 
       ≼_S _S(σ((y)))
    				 ≺ (u',_S(σ((y)))) 
       =μ(y).
 	_– End Proof Claim 2 –
	
	

	It remains to show (M2.iii), that is, if e_i=(x,y) is a transfer-edge, then
	μ(x) and μ(y) are incomparable in S. Since (x,y) is a transfer
	edge and by Condition (O3.b), σ((x)) ∩σ((y)) = ∅.
	If σ((x))={A} and σ((y))={C}, then μ(x) = (u,A)
	and μ(y) = (u',C). Since A and C are distinct leaves in S, μ(x)
	and μ(y) are incomparable.
	Assume that |σ((x))|>1. Hence, 
	there are leaves a,b ∈(x) with A = σ(a)≠σ(b)=B
	and c∈(y) with σ(c)=C≠ A,B. By construction, ab|c∈R_i and hence, AB|C∈𝒮(T;t,σ).
	The latter is fulfilled for all triples x'x”|c∈R_i with x',x”∈(x), 
	and, therefore, _S(σ((x))∪{C}) ≻_S _S(σ((x))).
	Set v=_S(σ((x))∪{C}).
	Thus, there is an edge (v,v') in S
	with v'≽_S _S(σ((x))) and an edge (v,v”)  such that v”≽_S C. 
	Hence, either μ(x) = (v,v') or μ(x) = (u,_S(σ((x))) and v'≽_S u. 
	Assume that σ((y)) contains only the species C 
	and thus,  μ(y) = (u',C). 
	Since v”≽_S C, we have either 
	v” =  C which implies that μ(y) = (v,v”) or 
	v”≻_S  C which implies that μ(y) = (u',C) and v”≽_S u'. 
	Since both vertices v' and v” are incomparable in S, 
	so μ(x) and μ(y) are.
  	If |σ((y))|>1, then we set  v=_S(σ((x))∪σ((y)))
	and we can argue analogously as above and conclude that there are edges 
	(v,v') and (v,v”) in S such that 
	v'≽_S _S(σ((x)))  and 
	v”≽_S _S(σ((y))).
	Again, 
	since v' and v” are incomparable in S and by construction of μ, 
	μ(x) and μ(y) are incomparable.





Lemma <ref> implies that consistency of the triple set
𝒮(T; t,σ ) is necessary for the existence of a reconciliation
map from (T; t,σ ) to a species tree on . Lemma
<ref>, on the other hand, establishes that this is also
sufficient. Thus, we have

	There is a species tree on = σ() for a  gene tree 
	(T;t, σ) on  if
	and only if the triple set 𝒮(T; t,σ ) is consistent.






 §.§ Non-Binary Gene Trees






Now, we consider arbitrary, possibly non-binary gene trees that might be used  
to model incomplete knowledge of the exact genes phylogeny. 
Consider the “true” history of a gene tree that evolves along the (tube-like)
species tree in Figure <ref> (left).
The observable gene tree (T;t,σ) is shown in  
<ref> (center-left). Since 
 ab|c,b'c'|a'∈R_0, 
 we obtain a set of  
species triples 𝒮(T;t,σ) that contain the pair of 
inconsistent species triple AB|C,BC|A. Thus, 
there is no reconciliation map for 
(T;t,σ) and any species tree, 
although (T;t,σ) is biologically feasible. 
Consider now 
the “orthology” graph G (shown below the gene trees) that 
has as vertex set  and two genes x,y are connected by an edge if (x,y) is a 
speciation vertex. Such graphs can be obtained from orthology
inference methods <cit.> 
and the corresponding non-binary 
gene tree  (T';t,σ) (center-right) is constructed from such estimates
 (see <cit.> for further
    details).
Still, we can see that  𝒮(T';t,σ) contains the two 
inconsistent species triples AB|C,BC|A. However, there is 
a reconciliation map μ according to 
Definition <ref> and a species tree S, as shown in 
Figure <ref> (right). 
Thus, consistency of  𝒮(T';t,σ)  does not characterize whether there
is a valid reconciliation map for non-binary gene trees.


In order to obtain a similar result as in Theorem <ref> for non-binary 
gene trees we have to strengthen observability axiom (O3.a) to 

  (O3.A) 





		If x is a speciation vertex with children v_1,…,v_k, then 
		(v_i) ∩(v_j) =∅,  1≤ i<j≤ k; 


























and to add an extra event constraint to Definition <ref>: 
	
  (M2.iv)  Let v_1,…,v_k be the children of the speciation vertex x. 
						 Then, μ(v_i) and μ(v_j) are incomparable in S, 1≤ i<j≤ k.
 


We call a reconciliation map that additionally satisfies (M2.iv) a  restricted reconciliation map.
Such restricted reconciliation maps 
satisfy the condition as required in <cit.> for the HGT-free case.  
It can be shown that restricted reconciliation maps imply Condition (O3.A), 
however, the converse is not true in general, see Figure <ref>.
Hence, we cannot use the axioms (O1)-(O3) and (O3.A)
to derive Condition (M2.iv)  - similar to Lemma <ref>(<ref>) 
- and thus, need to claim it. 


 

It is now straightforward to obtain the next result. 

	If μ is a restricted reconciliation map 
   from (T;t,σ) to S
	and ab|c∈ℛ(T;t,σ), then 
	σ(a)σ(b)|σ(c) is displayed in S.
  


	Let {a,b,c}∈3 and assume w.l.o.g. ab|c∈ℛ(T;t,σ).

	First assume that ab|c∈R_0, that is ab|c is displayed
	in  and t(_(a,b,c)) =. For simplicity set
	u=_(a,b,c). Hence, there are two children  x,y of u in 
	such that  w.l.o.g. a,b∈ L_(x) and c∈ L_(y). 	
	Now we can argue analogously as in the proof of Lemma <ref>  
	after replacing “we can apply 	Lemma <ref>(<ref>) ”
	by “we can apply Condition (M2.iv)”. 
	The proof for ab|c∈R_i remains the same as in  Lemma <ref>.



























	
	Let S be a species tree on . 
	Then, there is a restricted reconciliation map 	μ  from a  gene tree (T;t,σ) 
   that satisfies also (O3.A) to S
	whenever S displays all triples in 𝒮(T;t,σ).



	The proof is similar to the proof of Lemma <ref>. 
	However, note that a speciation vertex might have more than two children. 
	In these cases, one simply has to apply
	 Axiom (O3.A) instead of Lemma (O3.a)
	to conclude that (M1),(M2.i)-(M2.iii), (M3) are
	satisfied. 

	It remains to show that 	(M2.iv) is satisfied. 
	To this end, let x be a speciation vertex in T and the set of its children
	C(x) = {v_1,…,v_k}. 
	By axiom (O3.A) we have	(v_i) ∩(v_j) =∅ for all i≠ j.
	Consider the following partition of C(x) into C_1 and C_2 that contain
    all vertices v_i with |(v_i)|=1 and |(v_i)|>1, respectively. 
	By construction of μ, for all vertices in v_i,v_j∈ C_1, i≠ j
	we have that μ(v_i)∈{σ(v_i), (u,σ(v_i)) } and 
	μ(v_j)∈{σ(v_j), (u',σ(v_j)) }  are incomparable. 
	Now let  v_i∈ C_1 and  v_j∈ C_2. Thus there are A,B∈(v_j)
	and σ(v_i)=C. Hence, AB|C∈𝒮(T;t,σ)
	Thus, _S(A,B)	must be incomparable to C in S. 
	Since the latter is satsfied for all species in (v_j), 	
    _S( (v_j))	and C must be incomparable in S. 
	Again, by construction of μ, we see that 
	μ(v_i)∈{C, (u,C) } and 
	μ(v_j)∈{_S( (v_j)), (u',_S( (v_j))) }
	are incomparable in S. 
	Analogously, if v_i,v_j∈ C_2, i≠ j, then 
    all triples AB|C and CD|A for all A,B∈(v_j)
	and C,D∈(v_j) are contained in 𝒮(T;t,σ)
	and thus, displayed by S. 
	Hence, _S( (v_i))	 and _S( (v_j))	
	must be incomparable in S. Again, by construction of μ, 
	we obtain that μ(v_i)∈{_S( (v_i)), (u,_S( (v_i))) } and 
	μ(v_j)∈{_S( (v_j)), (u',_S( (v_j))) }
	are incomparable in S. Therefore, (M2.iv) is satisfied. 










































































As in the binary case, we obtain

	There is a restricted reconciliation map for 
	a gene tree (T;t, σ) on  that satisfies also (O3.A) and some species tree on
	= σ() if
	and only if the triple set 𝒮(T; t,σ ) is consistent.


	




 §.§ Algorithm



The proof of Lemma <ref> and <ref> is constructive and we summarize the
latter findings in Algorithm <ref>, see Figure <ref> for an
illustrative example. 
 

		 Algorithm <ref> returns a species tree S for a binary gene tree (T;t,σ) 
		 and a reconciliation map μ in polynomial time, if one exists
		 and otherwise, returns that there is no species tree for (T;t,σ).

		If (T;t,σ) is non-binary but satisfies Condition (O3.A), 
	   then Algorithm <ref> returns a species tree S for (T;t,σ) 
		 and a  restricted reconciliation map μ in polynomial time, if one exists
		 and otherwise, returns that there is no species tree for (T;t,σ).


	Theorem  <ref> and the construction of μ in the proof of Lemma
	<ref> and <ref> implies the correctness of the algorithm. 
	
	For the runtime observe that all tasks, computing 𝒮(T;t,σ), using the 
	 algorithm <cit.> and  the construction of the map
	μ <cit.> can be done  in polynomial time. 










In our examples, the species trees that display 𝒮(T; t,σ ) is
computed using the O(|L_R||R|) time algorithm , that either
constructs a tree S that displays all triples in a given triple set R or
recognizes that R is not consistent. However, any other supertree method might
be conceivable, see <cit.> for an overview. The tree T returned
by  is least resolved, i.e., if T' is obtained from T by
contracting an edge, then T' does not display R anymore. However, the trees
generated by  do not necessarily have the minimum number of
internal vertices, i.e., the trees may resolve multifurcations in an arbitrary
way that is not implied by any of the triples in R. Thus, depending on R,
not all trees consistent with R can be obtained from . 
Nevertheless, in <cit.> the following result was
established. 

	Let R be a consistent triple set.
	If the tree T obtained with  applied on R is binary, 
	then T is a unique tree on L_R that displays R, i.e., for any tree T' on L_R 
	that displays  R we have T'≃ T.
	




So-far, we have shown that event-labeled gene trees (T;t,σ) for
which a species tree exists can be characterized by a set of species triples
S(T;t,σ) that is easily constructed from a subset of triples
displayed in T. From a biological point of view, however, it is necessary to
reconcile a gene tree with a species tree such that genes do not “travel
through time”. In <cit.>, the authors gave algorithms
to check whether a given
reconciliation map μ is time-consistent, and an algorithm with the same
time complexity for the construction of a time-consistent reconciliation
maps, provided one exists.
These algorithms require as input an event-labeled gene tree and species tree. 
Hence, a necessary condition for the existence of time-consistent reconciliation maps is given by
consistency of the species triple S(T;t,σ) derived from (T;t,σ).
However, there are
possibly exponentially many species trees that are consistent with S(T;t,σ) for which some
of them have a time-consistent reconciliation map with T and some not, see Figure <ref>. The
question therefore arises as whether there is at least one species tree S with time-consistent
map, and if so, construct S. 







§ LIMITATIONS OF INFORMATIVE TRIPLES AND RECONCILIATION MAPS





In Section <ref> we have already discussed that consistency of 
S(T;t,σ) cannot be used to characterize whether there 
is a reconciliation map  that doesn't need to satisfy (M2.iv) 
for some non-binary gene tree, see Figure <ref>.
In particular, Figure <ref> 
 shows a biologically feasible binary  gene trees (center-left)
for which, however, neither a reconciliation map nor a restricted reconciliation map
exists.  
Therefore, reconciliation maps provide, unsurprisingly, only a sufficient but not necessary condition
to determine whether  gene trees are biologically feasible.
A further simple example is given in Figure <ref>.
Consider the “true” history of the gene tree that evolves along the (tube-like)
species tree in Figure <ref> (left). The set of extant genes
 comprises a,a',b,b',c and c' and σ maps each gene in  to
the species (capitals below the genes) A,B,C∈. For the observable gene
tree (T;t,σ) in Figure <ref> (center) we observe
that  R_0 = {ab|c,b'c'|a'} and thus, 
one obtains
the inconsistent species triples S(T;t,σ) = {AB|C,BC|A}.
Hence, Theorem <ref> implies that there is no species tree for
(T;t,σ). Note,  (T;t,σ) satisfies also Condition (O3.A). 
Hence, Theorem <ref> implies that no restricted reconciliation
map to any species tree exists for (T;t,σ).
Nevertheless, (T;t,σ) is biologically feasible as there is a
true scenario that explains the gene tree.


If Condition (M2.i) would be relaxed, that is, if we allow for speciation
vertices u that μ(u) ≽_S _S((u)), then there is a relaxed
μ from (T;t,σ) to the species tree S shown in Figure
<ref> (right). Hence, consistency of S(T;t,σ)
does not characterize the existence of relaxed reconciliation maps. 










§ CONCLUSION AND OPEN PROBLEMS

	
	Event-labeled gene trees can be obtained by combining the reconstruction of
	gene phylogenies with methods for orthology and HGT detection. We showed that
	event-labeled gene trees (T;t,σ) for which a species tree exists can be
	characterized by a set of species triples S(T;t,σ) that is easily
	constructed from a subset of triples displayed in T.

	We have shown that  biological feasibility of  gene trees cannot be explained 
	in general by reconciliation maps, that is, there are biologically feasible gene trees
	for which no reconciliation map to any species tree exists. 
	Moreover, we showed that consistency of S(T;t,σ) does not characterize
	the existence of relaxed reconciliation maps. 




	 We close this contribution by stating some open problems that need to be
	solved in future work. 

	(1) Are all event-labeled gene trees (T;t,σ) biologically feasible?
		
		(2) The results established here are based on informative triples provided by the gene trees. 
					  If it is desired to find “non-restricted” reconciliation maps (those for which Condition (M2.iv) is not required) 
						for non-binary gene trees
					  the following question needs to be answered:
   					How much information of a non-restricted reconciliation map and a species tree 
		    			is already contained in non-binary event-labeled  gene trees (T;t,σ)?
					The latter might also be generalized by considering  relaxed reconciliation maps (those for which 
					μ(x)≻_S _S((x)) for speciation vertices x or any other relaxation is allowed).                





	

	(3) Our results depend on three axioms (O1)-(O3) on the event-labeled
		         gene trees that are motivated by the fact that event-labels can
		         be assigned to internal vertices of gene trees only if there is
		         observable information on the event. The question which
		         event-labeled gene trees are actually observable given an
		         arbitrary, true evolutionary scenario deserves further
		         investigation in future work, since a formal theory of
		         observability is still missing.

	(4) The definition of reconciliation maps is 
					by no means consistent in the literature. 
					For the results established here we considered three types of 
					  reconciliation maps, that is, the “usual” map as in Def. <ref>
                 (as used in e.g. <cit.>), a restricted version (as used in e.g. <cit.>)
						and a relaxed version. 
				   However, a unified framework for reconciliation maps is desirable and might
					be linked with a formal theory of   observability.


	(5) “Satisfiable” event-relations R_1,…,R_k are those for which there is a 
						representing gene tree (T;t,σ)
						such that (x,y)∈ R_i if and only if t((x,y))=i. They are equivalent to 
						so-called unp 2-structures <cit.>. 
					 	In particular, if event-relations consist of orthologs, paralogs and xenologs only, then
						satisfiable event-relations are equivalent to directed cographs <cit.>. 
						Satisfiable event-relations R_1,…,R_k are “S-consistent” if there is a species tree S
						for the representing gene tree (T;t,σ) <cit.>. 
						However, given the unavoidable noise in the input data and possible
						uncertainty about the true relationship between two genes, 
						one might ask to what extent the work of Lafond et al. <cit.>
						can be generalized to determine whether given “partial” event-relations 
						are S-consistent or not. 
						It is assumable that subsets of the informative
						species triples S(T;t,σ) that might be directly computed from such
						event-relations can offer an avenue to the latter problem.
						Characterization and complexity results for 
						“partial” event-relations to be satisfiable have been addressed in  <cit.>.

		(6) In order to determine whether there is a time-consistent reconciliation map
					for some given event-labeled gene tree and species 
					trees fast algorithms have been developed <cit.>. 
					 However, these algorithms require as input a gene tree (T;t,σ)
					and a species tree S. 	
					A necessary condition to a have time-consistent (restricted) reconciliation map
					to some species tree is given by the consistency of the species triples 𝒮(T;t,σ). 
					However, in general there might be
					exponentially many species trees that display 𝒮(T;t,σ) for which
					some of them may have a time-consistent reconciliation map with (T;t,σ) and some might have
					not (see Figure <ref> or <cit.>). Therefore, additional constraints to determine whether 
					there is at least one species tree S with time-consistent
					map, and if so, construct S, must be established. 

		(7)	A further key problem is the identification of horizontal transfer events. 
						In principle, likely genes that have been introduced into a genome by HGT
					   can be identified directly from sequence data <cit.>. Sequence
						composition often identifies a gene as a recent addition to a genome. In the absence
					   of horizontal transfer, the similarities of pairs of true orthologs in the species pairs
						(A,B) and (A,C) are expected to be linearly correlated. Outliers are likely candidates for
						HGT events and thus can be “relabeled”. However, a 
						more detailed analysis of the relational properties of horizontally 
						transferred genes is needed.


plain

