Describing the local structure of sequence graphs (Q2364898)

In this paper the authors present an extended definition of ultrabubbles, for describing sites of genetic variation that may be used for indexing or querying variants in alleles. Following a brief description of background concepts, the authors overview the difficulties in defining the VCF sites in graphs and the usage of directed and bidirected sequence graphs for modelling this problem. Next, the bubbles, superbubbles, ultrabubbles and snarls are introduced in the context of graphs which are decomposable into nested simple sites (the features of graphs which do not admit decomposition into sites are also discussed). The next section of the paper focuses on abutting variants (bundles) and includes an algorithm for finding such bundles. The difficulties in defining their boundaries (and the boundaries of snarls) as well as the definition of a special class for handling bundles with deletions are included. For the entire collection see [Zbl 1365.92002].