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

Link identifier archive #link-archive-thumb-soap-32564
A family of tree-based generators for bubbles in directed graphs
Venerdì 30 aprile 2021 alle ore 15:00, la prof.ssa Blerina Sinaimeri (LUISS) presenterà il seminario di Logica e Informatica Teorica dal titolo: "A family of tree-based generators for bubbles in directed graphs". 

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. 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 identifier #identifier__102130-1Link.
Link identifier #identifier__65106-1Link identifier #identifier__171845-2Link identifier #identifier__89521-3Link identifier #identifier__56168-4