Alternative Characterizations of Fitch's Xenology Relation

Abstract

According to Walter M. Fitch, two genes are xenologs if they are separated by at least one horizontal gene transfer. 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 least 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. In this contribution, we provide two novel characterizations of Fitch relations and present an alternative, short and elegant proof of the characterization theorem established by Geiß et al.\ in \emph{J.\ Math.\ Bio 77(5), 2018}.

References in corpus (1)

• Phylogenomics with Paralogs

Cited by in corpus (3)

• Generalized Fitch Graphs II: Sets of Binary Relations that are explained by Edge-labeled Trees
• Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
• Orientation of Fitch Graphs and Detection of Horizontal Gene Transfer in Gene Trees