Seminari del Dipartimento


Logica e Informatica Teorica

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

Blerina Sinaimeri

30-04-2021 - 15:00
modalitĂ  telematica (telematic form)


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. In this talk we present 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. 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. We present some applications of the bubble generator on a real RNA-seq dataset and we conclude with some open problems.

[1] V. Acuña, R. Grossi, G. Italiano, L. De Lima, R. Rizzi, G. Sacomoto, M.-F. Sagot and B. Sinaimeri. On Bubble Generators in Directed Graphs, Algorithmica , 82(4): 898-914, 2020.
[2] V. Acuña, G. Italiano, L. De Lima, L. Pepè Sciarria, M.-F. Sagot and B. Sinaimeri. A family of tree-based generators for bubbles in directed graphs, 31rd International Workshop on Combinatorial Algorithms, IWOCA 2020 , Bordeaux, France, June 8-10, 2020.

Per partecipare al Seminario, cliccare sul seguente Link:
org: BONIFACI Vincenzo

Copyright© 2014 Dipartimento di Matematica e Fisica