Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Reconstructing gene trees from Fitch’s xenology relation
 Journal of mathematical biology 77 (2018), No.5, pp.14591491 ISSN: 03036812 ISSN: 14321416 

 English 
 Journal Article 
 Fraunhofer IZI () 
 fitch xenology; phylogenetic tree; leastresolved tree; rooted triple; informative triple set; dicograph; heritable graph property; forbidden induced subgraphs; recognition algorithm; fixed parameter tractable 
Abstract
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 nonsymmetric 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 leastresolved edgelabeled phylogenetic tree. We provide a lineartime algorithm for the recognition of xenology relations and for the construction of its leastresolved edgelabeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has farreaching consequences on approximation problems associated with xenology relations.