The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
From MaRDI portal
(Redirected from Publication:2014353)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 1478125 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Complement reducible graphs
- Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Fully dynamic recognition algorithm and certificate for directed cographs
- Graph Classes: A Survey
- Linear-time modular decomposition of directed graphs
- On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
- Orthology relation and gene tree correction: complexity results
- Orthology relations, symbolic ultrametrics, and cographs
- Primitivity is hereditary for 2-structures
- Recovering symbolically dated, rooted trees from symbolic ultrametrics
- The Recognition of Series Parallel Digraphs
- Theory of 2-structures
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
Cited in
(26)- Cograph editing: Merging modules is equivalent to editing P_4s
- Reconstructing gene trees from Fitch's xenology relation
- Computing directed Steiner path covers
- 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
- On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
- 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
- Orthology relations, symbolic ultrametrics, and cographs
- Partial homology relations -- satisfiability in terms of di-cographs
- Reciprocal best match graphs
- Alternative characterizations of Fitch's xenology relation
- Forbidden time travel: characterization of time-consistent tree reconciliation maps
- 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
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)
