Name
Abstract | ||
|---|---|---|
Bubbles are pairs of internally vertex-disjoint (s, t)-paths in a directed graph, which have many applications in the processing of DNA and RNA data. 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 bubble generator set, i.e., a polynomial-sized subset of bubbles from which all the other bubbles can be obtained through a suitable application of a specific symmetric difference operator. This set provides a compact representation of the bubble space of a graph. A bubble generator can be useful in practice, since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. 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. Finally, we present two applications of the bubble generator on a real RNA-seq dataset. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00453-019-00619-z | Algorithmica |
Keywords | Field | DocType |
Bubbles, Bubble generator set, Decomposition algorithm | Graph,Discrete mathematics,Symmetric difference,Exponential function,Directed graph,Compact space,Operator (computer programming),Mathematics,Bubble | Journal |
Volume | Issue | ISSN |
82 | 4 | 0178-4617 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vicente Acuña | 1 | 84 | 7.94 |
| Roberto Grossi | 2 | 174 | 12.29 |
| Giuseppe F. Italiano | 3 | 2364 | 254.07 |
| Leandro Lima | 4 | 2 | 1.40 |
| Romeo Rizzi | 5 | 895 | 100.75 |
| Gustavo Sacomoto | 6 | 45 | 5.81 |
| Marie-France Sagot | 7 | 1337 | 109.23 |
| B. Sinaimeri | 8 | 47 | 11.75 |