Combining Orthology and Xenology Data in a Common Phylogenetic Tree

Abstract

A rooted tree $T$ with vertex labels $t(v)$ and set-valued edge labels $\lambda (e)$ defines maps $\delta$ and $\epsilon$ on the pairs of leaves of $T$ by setting $\delta (x,y)=q$ if the last common ancestor $\text{lca}(x,y)$ of $x$ and $y$ is labeled $q$, and $m\in \epsilon (x,y)$ if $m\in \lambda (e)$ for at least one edge $e$ along the path from $\text{lca}(x,y)$ to $y$. We show that a pair of maps $(\delta ,\epsilon )$ derives from a tree $(T,t,\lambda )$ 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_{\epsilon },{\lambda }_{\epsilon })$ that explains $\epsilon$ (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.