Artículo de revista
On bubble generators in directed graphs
Fecha
2017Registro en:
Lecture Notes in Computer Science (LNCS, volume 10520), 2017
16113349
03029743
10.1007/978-3-319-68705-6_2
Autor
Acuña Aguayo, Vicente
Grossi, Roberto
Italiano, Giuseppe F.
Lima, Leandro
Rizzi, Romeo
Sacomoto, Gustavo
Sagot, Marie France
Sinaimeri, Blerina
Institución
Resumen
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.