COMPUTER SCIENCE COLLOQUIUM
The Fitch Relation
Marc Hellmuth
Department of Mathematics and Computer Science
University of Greifswald, Germany
Thursday, 12 April, 2018 at 14:15
IMADA's Seminar Room
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 phylogenetic trees.
Host: Daniel Merkle
SDU HOME |
IMADA HOME |
Previous Page
Daniel Merkle
