# Efficient Bubble Enumeration in Directed Graphs

* Auteur correspondant
4 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive
Abstract : Polymorphisms in DNA- or RNA-seq data lead to recognisable patterns in a de Bruijn graph representation of the reads obtained by sequencing. such patterns have been called mouths, or bubbles in the literature. They correspond to two vertex-disjoint directed paths between a source $s$ and a target $t$. Due to the high number of such bubbles that may be present in real data, their enumeration is a major issue concerning the efficiency of dedicated algorithms. We propose in this paper the first linear delay algorithm to enumerate all bubbles with a given source.
Type de document :
Communication dans un congrès
String Processing and Information Retrieval (SPIRE), Oct 2012, Cartagena, Colombia. 7608, pp.118-129, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-34109-0_13>
Domaine :

https://hal.inria.fr/hal-00738927
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 5 octobre 2012 - 13:54:03
Dernière modification le : jeudi 9 février 2017 - 15:48:38
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 21:15:14

### Fichier

article15_spire.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Etienne Birmelé, Pierluigi Crescenzi, Rui Ferreira, Roberto Grossi, Vincent Lacroix, et al.. Efficient Bubble Enumeration in Directed Graphs. String Processing and Information Retrieval (SPIRE), Oct 2012, Cartagena, Colombia. 7608, pp.118-129, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-34109-0_13>. <hal-00738927>

Consultations de
la notice

## 289

Téléchargements du document