Marc Hellmuth: The Mathematics of Horizontal Gene Transfer and Fitch's Xenology Relation

Abstract

Horizontal Gene Transfer (HGT) is the movement of genetic material between coexisting species. Given the true history of the genes, Walter M. Fitch defined in his illuminating paper (Trends Genet. 16(5), 2000) two genes as “xenologs” if their history since their common ancestor involves HGT of at least one of them. Although this definition of xenology is one of the most commonly used terms in phylogenomics, the mathematics of the xenology-relation X has not been investigated in detail, so-far. In this talk, we consider the following two problems:

(1) How much phylogenetic signal is contained in a xenology-relation X? In other words, is it possible to infer phylogenetic trees from X?  

(2) Can we characterize xenology-relations? In other words, is it possible to decide whether an arbitrary binary relation is a xenology-relation?  

To this end, we study the graph structure of the relation X. Surprisingly, xenology-relations are characterized by a small set of forbidden induced subgraphs on three vertices and they form a subclass of so-called directed cographs. We provide a linear-time algorithm to recognize such relations and for the reconstruction of least-resolved phylogenetic trees.