Combining Orthology and Xenology Data in a Common Phylogenetic Tree

In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels \(\lambda (e)\). The orthology and paralogy relations between genes are a special case of a map \(\delta \) on the pairs of leaves of T defined by \(\delta (x,y)=q\) if the last common ancestor \({\text {lca}}(x,y)\) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map \(\varepsilon \) with \(m\in \varepsilon (x,y)\) if \(m\in \lambda (e)\) for at least one edge e along the path from \({\text {lca}}(x,y)\) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps \((\delta ,\varepsilon )\) derives from a tree \((T,t,\lambda )\) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree \((T_{\delta },t_{\delta })\) that explains \(\delta \) and the (unique) least-resolved edge labeled tree \((T_{\varepsilon },\lambda _{\varepsilon })\) that explains \(\varepsilon \) (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.