Orthology relations, symbolic ultrametrics, and cographs
From MaRDI portal
Publication:1937881
DOI10.1007/s00285-012-0525-xzbMath1408.05038OpenAlexW2041346050WikidataQ45375976 ScholiaQ45375976MaRDI QIDQ1937881
Maribel Hernandez-Rosales, Peter F. Stadler, Katharina T. Huber, Nicolas Wieseke, Marc Hellmuth, Vincent L. Moulton
Publication date: 1 February 2013
Published in: Journal of Mathematical Biology (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00285-012-0525-x
Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)
Related Items
Orthology Relation and Gene Tree Correction: Complexity Results ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ Complete characterization of incorrect orthology assignments in best match graphs ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Complexity of modification problems for best match graphs ⋮ Reconstructing unrooted phylogenetic trees from symbolic ternary metrics ⋮ Complete edge-colored permutation graphs ⋮ Best match graphs ⋮ Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Injective split systems ⋮ Exact-2-relation graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Spiders can be recognized by counting their legs ⋮ Beyond representing orthology relations by trees ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ Inferring phylogenetic trees from the knowledge of rare evolutionary events ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ Indirect identification of horizontal gene transfer ⋮ Complexity of modification problems for reciprocal best match graphs ⋮ Reciprocal best match graphs ⋮ Best match graphs and reconciliation of gene trees with species trees ⋮ Three-way symbolic tree-maps and ultrametrics ⋮ Defining and identifying cograph communities in complex networks ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- New results on optimizing rooted triplets consistency
- Complement reducible graphs
- Recovering symbolically dated, rooted trees from symbolic ultrametrics
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- A supertree method for rooted trees
- Applying modular decomposition to parameterized cluster editing problems
- Cograph Editing: Complexity and Parameterized Algorithms
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
