Least resolved trees for two-colored best match graphs

DOI10.7155/JGAA.00564MaRDI QIDQ5084685zbMATH OpenOpenAlexFDO

Authors David Schaller, Manuela Geiß, Marc Hellmuth, Peter F. Stadler

Publication date 28 June 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90)

Abstract: 2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive graphs that appears in phylogenetic combinatorics. There, 2-BMGs describe evolutionarily most closely related genes between a pair of species. They are explained by a unique least resolved tree (LRT). Introducing the concept of support vertices we derive an $O(|V|+|E|lo{g}^2|V|)$-time algorithm to recognize 2-BMGs and to construct its LRT. The approach can be extended to also recognize binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.

Recommendations

• The structure of 2-colored best match graphs
• Best match graphs
• Quasi-best match graphs
• Best match graphs with binary trees
• Reciprocal best match graphs

Cites work

• An On-Line Edge-Deletion Problem
• Best match graphs
• Best match graphs with binary trees
• Complete characterization of incorrect orthology assignments in best match graphs
• Complexity of modification problems for best match graphs
• Corrigendum to: ``Best match graphs
• Generating a random sink-free orientation in quadratic time
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Introduction to algorithms
• Oriented bipartite graphs and the Goldbach graph
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• The graph menagerie: abstract algebra and the mad veterinarian
• The structure of 2-colored best match graphs

Cited in

(4)

• Best match graphs with binary trees
• The structure of 2-colored best match graphs
• Best match graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

Describes a project that uses

Uses Software

• NetworkX

This page was built for publication: Least resolved trees for two-colored best match graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084685)