Reconstructing gene trees from Fitch's xenology relation

DOI10.1007/s00285-018-1260-8zbMath1396.05025arXiv1711.02152OpenAlexW2964266490WikidataQ64123993 ScholiaQ64123993MaRDI QIDQ1789081

Manuela Geiß, Marc Hellmuth, Nicolas Wieseke, John Anders, Peter F. Stadler

Publication date: 9 October 2018

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

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

zbMATH Keywords

forbidden induced subgraphsphylogenetic treerecognition algorithmfixed parameter tractabledi-cographFitch xenologyheritable graph propertyinformative triple setsleast-resolved treerooted triples

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Compatibility of partitions with trees, hierarchies, and split systems ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ 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 ⋮ Exact-2-relation graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ A short note on undirected Fitch graphs ⋮ Indirect identification of horizontal gene transfer ⋮ Reciprocal best match graphs ⋮ Best match graphs and reconciliation of gene trees with species trees ⋮ Best match graphs with binary 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Rooted maximum agreement supertrees
• Primitivity is hereditary for 2-structures
• The node-deletion problem for hereditary properties is NP-complete
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• The matroid structure of representative triple sets and triple-closure computation
• Linear-time modular decomposition of directed graphs
• Partial homology relations -- satisfiability in terms of di-cographs
• Extension operations on sets of leaf-labelled trees
• Orthology relations, symbolic ultrametrics, and cographs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Closure operations in phylogenetics
• Fully dynamic recognition algorithm and certificate for directed cographs
• Phylogeny
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Forbidden time travel: Characterization of time-consistent tree reconciliation maps
• A short note on undirected Fitch graphs
• Orthology Relation and Gene Tree Correction: Complexity Results
• Fast Compatibility Testing for Rooted Phylogenetic Trees
• Node-and edge-deletion NP-complete problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity