# Efficient Bubble Enumeration in Directed Graphs

* Corresponding author
4 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
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.
Document type :
Conference papers
Domain :
Complete list of metadatas

Cited literature [12 references]

https://hal.inria.fr/hal-00738927
Contributor : Marie-France Sagot <>
Submitted on : Friday, October 5, 2012 - 1:54:03 PM
Last modification on : Friday, September 27, 2019 - 10:10:14 AM
Long-term archiving on : Friday, December 16, 2016 - 9:15:14 PM

### File

article15_spire.pdf
Files produced by the author(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. pp.118-129, ⟨10.1007/978-3-642-34109-0_13⟩. ⟨hal-00738927⟩

Record views