Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Reconstructing gene trees from Fitch’s xenology relation

: Geiß, Manuela; Anders, John; Stadler, Peter F.; Wieseke, Nicolas; Hellmuth, Marc


Journal of mathematical biology 77 (2018), No.5, pp.1459-1491
ISSN: 0303-6812
ISSN: 1432-1416
Journal Article
Fraunhofer IZI ()
fitch xenology; phylogenetic tree; least-resolved tree; rooted triple; informative triple set; di-cograph; heritable graph property; forbidden induced subgraphs; recognition algorithm; fixed parameter tractable

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y.We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations.