  In the absence of horizontal gene transfer it is possible to reconstruct the
history of gene families from empirically determined orthology relations, which
are equivalent to event-labeled gene trees. Knowledge of the event labels
considerably simplifies the problem of reconciling a gene tree T with a species
trees S, relative to the reconciliation problem without prior knowledge of the
event types. It is well-known that optimal reconciliations in the unlabeled
case may violate time-consistency and thus are not biologically feasible. Here
we investigate the mathematical structure of the event labeled reconciliation
problem with horizontal transfer. We investigate the issue of time-consistency
for the event-labeled version of the reconciliation problem, provide a
convenient axiomatic framework, and derive a complete characterization of
time-consistent reconciliations. This characterization depends on certain weak
conditions on the event-labeled gene trees that reflect conditions under which
evolutionary events are observable at least in principle. We give an
O(|V(T)|log(|V(S)|))-time algorithm to decide whether a time-consistent
reconciliation map exists. It does not require the construction of explicit
timing maps, but relies entirely on the comparably easy task of checking
whether a small auxiliary graph is acyclic. The combinatorial characterization
of time consistency and thus biologically feasible reconciliation is an
important step towards the inference of gene family histories with horizontal
transfer from orthology data, i.e., without presupposed gene and species trees.
The fast algorithm to decide time consistency is useful in a broader context
because it constitutes an attractive component for all tools that address tree
reconciliation problems.
