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.
Liste complète des métadonnées

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01647516
Contributor : Marie-France Sagot <>
Submitted on : Friday, November 24, 2017 - 5:51:04 PM
Last modification on : Thursday, April 18, 2019 - 3:25:19 PM

File

On_Bubble_Generators_in_Direct...
Files produced by the author(s)

Identifiers

Collections

Citation

Vicente Acuna, Roberto Grossi, Giuseppe 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⟩

Share

Metrics

Record views

328

Files downloads

332