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
| CREATOR | Annachiara Korchmaros, Guillaume E. Scholz, Peter F. Stadler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-03592