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.
Type de document :
Communication dans un congrès
WG 2017 - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. Springer, 10520, pp.18-31, 2017, Lecture Notes in Computer Science. 〈10.1007/978-3-319-68705-6_2〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01647516
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 24 novembre 2017 - 17:51:04
Dernière modification le : jeudi 19 avril 2018 - 14:49:47

Fichier

On_Bubble_Generators_in_Direct...
Fichiers produits par l'(les) auteur(s)

Identifiants

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. Springer, 10520, pp.18-31, 2017, Lecture Notes in Computer Science. 〈10.1007/978-3-319-68705-6_2〉. 〈hal-01647516〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

17