title: The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations.
abstract: The concepts of orthology, paralogy, and xenology play a key role in molecular evolution. Orthology and paralogy distinguish whether a pair of genes originated by speciation or duplication. The corresponding binary relations on a set of genes form complementary cographs. Allowing more than two types of ancestral event types leads to symmetric symbolic ultrametrics. Horizontal gene transfer, which leads to xenologous gene pairs, however, is inherent asymmetric since one offspring copy "jumps" into another genome, while the other continues to be inherited vertically. We therefore explore here the mathematical structure of the non-symmetric generalization of symbolic ultrametrics. Our main results tie non-symmetric ultrametrics together with di-cographs (the directed generalization of cographs), so-called uniformly non-prime ([Formula: see text]) 2-structures, and hierarchical structures on the set of strong modules. This yields a characterization of relation structures that can be explained in terms of trees and types of ancestral events. This framework accommodates a horizontal-transfer relation in terms of an ancestral event and thus, is slightly different from the the most commonly used definition of xenology. As a first step towards a practical use, we present a simple polynomial-time recognition algorithm of [Formula: see text] 2-structures and investigate the computational complexity of several types of editing problems for [Formula: see text] 2-structures. We show, finally that these NP-complete problems can be solved exactly as Integer Linear Programs.
authors.affiliation: Department of Mathematics and Computer Science, University of Greifswald, Walther-Rathenau-Straße 47,  17487 , Greifswald, Germany. mhellmuth@mailbox.org.|Center for Bioinformatics, Saarland University, Building E 2.1, P.O. Box 151150, 66041 , Saarbrücken, Germany. mhellmuth@mailbox.org.
authors.forename: Marc
authors.initials: M
authors.lastname: Hellmuth
authors.affiliation: Bioinformatics Group, Department of Computer Science, University of Leipzig, Härtelstraße 16-18, 04107 , Leipzig, Germany.|Interdisciplinary Center of Bioinformatics, University of Leipzig, Härtelstraße 16-18, 04107 , Leipzig, Germany.|Max-Planck-Institute for Mathematics in the Sciences, Inselstraße 22, 04103 , Leipzig, Germany.|Institute of Theoretical Chemistry, University of Vienna, Währingerstraße 17, 1090 , Wien, Austria.|Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, 87501 , USA.
authors.forename: Peter F
authors.initials: PF
authors.lastname: Stadler
authors.affiliation: Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig, Johannisgasse 26, 04103 , Leipzig, Germany.|Interdisciplinary Center of Bioinformatics, University of Leipzig, Johannisgasse 26, 04103 , Leipzig, Germany.
authors.forename: Nicolas
authors.initials: N
authors.lastname: Wieseke
mesh_terms: D019143:Evolution, Molecular; D022761:Gene Transfer, Horizontal; D008954:Models, Biological; D010802:Phylogeny
keywords: 2-Structures; Di-cograph; Gene tree; Integer Linear Program; NP-completeness; Orthologs; Paralogs; Recognition algorithm; Symbolic ultrametric; Uniformly non-prime decomposition; Xenologs