Sökning: (WFRF:(Stadler Peter F.))
> (2020-2024) >
Quasi-best match gr...
Abstract
Ämnesord
Stäng
- Quasi-best match graphs (qBMGs) are a hereditary class of directed, properly vertex -colored graphs. They arise naturally in mathematical phylogenetics as a generalization of best match graphs, which formalize the notion of evolutionary closest relatedness of genes (vertices) in multiple species (vertex colors). They are explained by rooted trees whose leaves correspond to vertices. In contrast to BMGs, qBMGs represent only best matches at a restricted phylogenetic distance. We provide characterizations of qBMGs that give rise to polynomial-time recognition algorithms and identify the BMGs as the qBMGs that are color-sink-free. Furthermore, two-colored qBMGs are characterized as directed graphs satisfying three simple local conditions, two of which have appeared previously, namely bi-transitivity in the sense of Das et al. (2021) and a hierarchy-like structure of out-neighborhoods, i.e., N(x) n N(y) E {N(x), N(y), 0} for any two vertices x and y. Further results characterize qBMGs that can be explained by binary phylogenetic trees.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- Colored directed graphs
- Hierarchies
- Rooted trees
- Phylogenetic combinatorics
- Best matches
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas