Skip to Main content Skip to Navigation
Conference papers

On Bubble Generators in Directed Graphs

Abstract : Bubbles are pairs of internally vertex-disjoint (s, t)-paths with applications in the processing of DNA and RNA data. For example, enumerating alternative splicing events in a reference-free context can be done by enumerating all bubbles in a de Bruijn graph built from RNA-seq reads [16]. However, listing and analysing all bubbles in a given graph is usually unfeasible in practice, due to the exponential number of bubbles present in real data graphs. In this paper, we propose a notion of a bubble generator set, i.e. a polynomial-sized subset of bubbles from which all the others can be obtained through the application of a specific symmetric difference operator. This set provides a compact representation of the bubble space of a graph, which can be useful in practice since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. Furthermore, we provide a polynomial-time algorithm to decompose any bubble of a graph into the bubbles of such a generator in a tree-like fashion.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Friday, November 24, 2017 - 5:51:04 PM
Last modification on : Tuesday, May 17, 2022 - 2:50:02 PM


Files produced by the author(s)




Vicente Acuna, Roberto Grossi, Giuseppe F Italiano, Leandro Lima, Romeo Rizzi, et al.. On Bubble Generators in Directed Graphs. WG 2017 - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. pp.18-31, ⟨10.1007/978-3-319-68705-6_2⟩. ⟨hal-01647516⟩



Record views


Files downloads