Alternative characterizations of Fitch's xenology relation

Horizontal gene transfer (HGT) is an important factor for the evolution of prokaryotes as well as eukaryotes. According to Walter M. Fitch, two genes are xenologs if they are separated by at least one HGT. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs (x, y) of genes x and y for which y has been horizontally transferred at least once since it diverged from the last common ancestor of x and y. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. The mathematical characterization of Fitch relations is crucial to understand whether putative xenology relations are at least to some extent "biologically feasible". In this contribution, we provide two novel characterizations of Fitch relations. In particular, these results allow us directly to reconstruct gene trees (together with the location of the horizontal transfer events) that explain the underlying Fitch relation. As a biological side result, we can conclude that the phylogenetic signal to infer these gene trees is entirely contained in those pairs of genes x and y for which no directional transfer has been taken place in the common history of y and the last common ancestor of x and y. In other words, non-HGT events provide the essential information about the gene trees. In addition, we utilize the new characterizations to present an alternative, short and elegant proof of the characterization theorem established by Geiß et al. (J Math Bio 77(5), 2018).