Geodesic
A family of tree-based generators for bubbles in directed graphs
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 563-580.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Bubbles are pairs of internally vertex-disjoint $(s, t)$-paths in a directed graph. In de Bruijn graphs built from reads of RNA and DNA data, bubbles represent interesting biological events, such as alternative splicing (AS) and allelic differences (SNPs and indels). However, the set of all bubbles in a de Bruijn graph built from real data is usually too large to be efficiently enumerated and analysed in practice. In particular, despite significant research done in this area, listing bubbles still remains the main bottleneck for tools that detect AS events in a reference-free context. Recently, in [Acuña et al., Algorithmica 2020] the concept of a bubble generator was introduced as a way for obtaining a compact representation of the bubble space of a graph. Although this bubble generator was quite effective in finding AS events, preliminary experiments showed that it is about 5 times slower than state-of-art methods. In this paper we propose a new family of bubble generators which improve substantially on previous work: bubble generators in this new family are about two orders of magnitude faster and are still able to achieve similar precision in identifying AS events. To highlight the practical value of our new bubble generators, we also report some experimental results on real datasets. Keywords: bubble generator, directed graphs, alternative splicing
DOI : 10.7155/jgaa.00572
Keywords: bubble generator, directed graphs, alternative splicing 
@article{JGAA_2021_25_1_a25,
     author = {Vicente Acu\~na and Leandro Ishi Soares de Lima and Giuseppe Italiano and Luca Pep\`e Sciarria and Marie-France Sagot and Blerina Sinaimeri},
     title = {A family of tree-based generators for bubbles in directed graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {563--580},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00572},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00572/}
}
TY  - JOUR
AU  - Vicente Acuña
AU  - Leandro Ishi Soares de Lima
AU  - Giuseppe Italiano
AU  - Luca Pepè Sciarria
AU  - Marie-France Sagot
AU  - Blerina Sinaimeri
TI  - A family of tree-based generators for bubbles in directed graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 563
EP  - 580
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00572/
DO  - 10.7155/jgaa.00572
LA  - en
ID  - JGAA_2021_25_1_a25
ER  - 
%0 Journal Article
%A Vicente Acuña
%A Leandro Ishi Soares de Lima
%A Giuseppe Italiano
%A Luca Pepè Sciarria
%A Marie-France Sagot
%A Blerina Sinaimeri
%T A family of tree-based generators for bubbles in directed graphs
%J Journal of Graph Algorithms and Applications
%D 2021
%P 563-580
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00572/
%R 10.7155/jgaa.00572
%G en
%F JGAA_2021_25_1_a25
Vicente Acuña; Leandro Ishi Soares de Lima; Giuseppe Italiano; Luca Pepè Sciarria; Marie-France Sagot; Blerina Sinaimeri. A family of tree-based generators for bubbles in directed graphs. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 563-580. doi : 10.7155/jgaa.00572. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00572/

Cité par Sources :