Reciprocal best match graphs

DOI10.1007/S00285-019-01444-2zbMath1433.05303arXiv1903.07920OpenAlexW2987931166WikidataQ91131758 ScholiaQ91131758MaRDI QIDQ2299268

Manuela Geiß, Peter F. Stadler, Marc Hellmuth

Publication date: 21 February 2020

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

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

zbMATH Keywords

phylogenetic treevertex-colored graphhierarchically colored cographpairwise best hitreciprocal best match heuristics

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

Hierarchical and modularly-minimal vertex colorings ⋮ Complete characterization of incorrect orthology assignments in best match graphs ⋮ Complexity of modification problems for best match graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ The structure of 2-colored best match graphs ⋮ Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee ⋮ Indirect identification of horizontal gene transfer ⋮ Best match graphs and reconciliation of gene trees with species trees

Uses Software

• OrthoGNC
• QuartetS
• OMA

Cites Work

• Unnamed Item
• Combinatorial logarithm and point-determining cographs
• On the Cartesian skeleton and the factorization of the strong product of digraphs
• Complement reducible graphs
• A simple linear time algorithm for cograph recognition
• Reconstructing gene trees from Fitch's xenology relation
• Orthology relations, symbolic ultrametrics, and cographs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Alternative characterizations of Fitch's xenology relation
• Best match graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• The number of caterpillars
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Linear Recognition Algorithm for Cographs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Dacey Graphs
• Cardinal multiplication of structures with a reflexive relation

This page was built for publication: Reciprocal best match graphs