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

DOI10.1007/s00285-016-1084-3zbMath1368.05023arXiv1603.02467OpenAlexW2294558945WikidataQ50541297 ScholiaQ50541297MaRDI QIDQ2014353

Marc Hellmuth, Peter F. Stadler, Nicolas Wieseke

Publication date: 11 August 2017

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

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

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

Related Items

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

Uses Software

• Proteinortho

Cites Work

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