Characterizations of undirected 2-quasi best match graphs Journal: Discrete Mathematics

Annachiara Korchmaros, Guillaume E. Scholz, Peter F. Stadler · 2025

Read Characterizations of undirected 2-quasi best match graphs Journal: Discrete Mathematics by Annachiara Korchmaros, Guillaume E. Scholz, Peter F. Stadler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03592.txt.

Description

Annachiara Korchmaros, Guillaume E Scholz, and Peter F Stadler characterize a class of graphs that model gene matches between two species. Best match graphs arise in evolutionary biology when each gene picks its closest counterpart across species. A looser quasi variant, stripped of direction, is the subject here.

That class turns out to be exactly the bipartite graphs avoiding three named patterns. An equivalent test says every connected piece must hold a heart vertex linked to all vertices of the opposite color. A cubic-time algorithm recognizes such graphs and, when they pass, builds a labeled tree that explains them. Clean characterizations help biologists tell whether gene match data can truly arise from a shared family tree.

Catalog record

CREATORAnnachiara Korchmaros, Guillaume E. Scholz, Peter F. Stadler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-03592

Browse the full library · About the Tower of Babel