The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations

DOI10.1007/S00285-016-1084-3zbMATH Open1368.05023arXiv1603.02467OpenAlexW2294558945WikidataQ50541297 ScholiaQ50541297MaRDI QIDQ2014353FDOQ2014353

Marc Hellmuth, Peter F. Stadler, Nicolas Wieseke

Publication date: 11 August 2017

Published in: Journal of Mathematical Biology (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1603.02467

zbMATH Keywords

NP-completenessrecognition algorithminteger linear programorthologs2-structuressymbolic ultrametricgene treedi-cographparalogsuniformly non-prime decompositionxenologs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Classes: A Survey
• Complement reducible graphs
• The Recognition of Series Parallel Digraphs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Primitivity is hereditary for 2-structures
• Linear-time modular decomposition of directed graphs
• Theory of 2-structures. II: Representation through labeled tree families
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Orthology relations, symbolic ultrametrics, and cographs
• On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• Orthology Relation and Gene Tree Correction: Complexity Results
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• Theory of 2-structures

Cited In (23)

• Cograph editing: Merging modules is equivalent to editing P_4s
• Forbidden time travel: Characterization of time-consistent tree reconciliation maps
• Computing directed Steiner path covers
• Reconstructing gene trees from Fitch's xenology relation
• A short note on undirected Fitch graphs
• Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• Best match graphs and reconciliation of gene trees with species trees
• Solutions for subset sum problems with special digraph constraints
• Best match graphs
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Shared ancestry graphs and symbolic arboreal maps
• Indirect identification of horizontal gene transfer
• Reciprocal best match graphs
• Alternative characterizations of Fitch's xenology relation
• The knapsack problem with special neighbor constraints
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Complete edge-colored permutation graphs
• How to compute digraph width measures on directed co-graphs
• From modular decomposition trees to rooted median graphs
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Reconciling event-labeled gene trees with MUL-trees and species networks
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees

Uses Software

• Proteinortho

This page was built for publication: The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014353)