Combining Orthology and Xenology Data in a Common Phylogenetic Tree

Abstract

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.