Best match graphs

DOI10.1007/s00285-019-01332-9zbMath1415.92133arXiv1803.10989OpenAlexW3098656959WikidataQ64111509 ScholiaQ64111509MaRDI QIDQ2420450

Peter F. Stadler, Maribel Hernandez-Rosales, Dulce I. Valdivia, Marc Hellmuth, Manuela Geiß, Bärbel M. R. Stadler, Marcos González Laffitte, Alitzel López Sánchez, Edgar Chávez

Publication date: 6 June 2019

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

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

zbMATH Keywords

hierarchyHasse diagramreachable setssupertreescolored digraphphylogenetic combinatoricsrooted triples

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Genetics and epigenetics (92D10)

Related Items (14)

Complete characterization of incorrect orthology assignments in best match graphs ⋮ Least resolved trees for two-colored best match graphs ⋮ Complexity of modification problems for 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 ⋮ Quasi-best match graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ The structure of 2-colored best match graphs ⋮ Corrigendum to: ``Best match graphs ⋮ 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 ⋮ Best match graphs with binary trees

Uses Software

• Proteinortho
• OrthoGNC
• QuartetS
• OMA

Cites Work

• Unnamed Item
• On the Cartesian skeleton and the factorization of the strong product of digraphs
• A simple sub-quadratic algorithm for computing the subset partial order
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Fast compatibility testing for rooted phylogenetic trees
• An algorithm for transitive reduction of an acyclic graph
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• Reconstructing gene trees from Fitch's xenology relation
• Reconstructing minimal rooted trees.
• 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
• Point determination in graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• The Subset Partial Order: Computing and Combinatorics
• Cardinal multiplication of structures with a reflexive relation
• The Transitive Reduction of a Directed Graph

This page was built for publication: Best match graphs