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 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.

A family of tree-based generators for bubbles in directed graphs / Acuña, Vicente; Soares de Lima, Leandro Ishi; Italiano, Giuseppe F.; Pepè Sciarria, Luca; Sagot, Marie-France; Sinaimeri, Blerina. - In: JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS. - ISSN 1526-1719. - 25:1(2021), pp. 563-580. [10.7155/jgaa.00572]

A family of tree-based generators for bubbles in directed graphs

Italiano, Giuseppe F.;Sinaimeri, Blerina
2021

Abstract

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 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.
Bubble generator, directed graphs, alternative splicing
A family of tree-based generators for bubbles in directed graphs / Acuña, Vicente; Soares de Lima, Leandro Ishi; Italiano, Giuseppe F.; Pepè Sciarria, Luca; Sagot, Marie-France; Sinaimeri, Blerina. - In: JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS. - ISSN 1526-1719. - 25:1(2021), pp. 563-580. [10.7155/jgaa.00572]
File in questo prodotto:
File Dimensione Formato  
572.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 601.14 kB
Formato Adobe PDF
601.14 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/211721
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact