Efficient Bubble Enumeration in Directed Graphs

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.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

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)

Identifiers

Collections

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⟩

Share

Metrics

Record views

518

Files downloads

754