title: A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs.
abstract: BACKGROUND
  The problem of enumerating bubbles with length constraints in directed graphs arises in transcriptomics where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq.
  
  
  RESULTS
  We present a new algorithm for enumerating bubbles with length constraints in weighted directed graphs. This is the first polynomial delay algorithm for this problem and we show that in practice, it is faster than previous approaches.
  
  
  CONCLUSIONS
  This settles one of the main open questions from Sacomoto et al. (BMC Bioinform 13:5, 2012). Moreover, the new algorithm allows us to deal with larger instances and possibly detect longer alternative splicing events.
authors.affiliation: INRIA Rhône-Alpes, 38330 Montbonnot Saint-Martin, France ; Université de Lyon, 69000 Lyon, France ; Université Lyon 1, Lyon, France ; CNRS, UMR5558, Laboratoire de Biométrie et Biologie Evolutive, 69622 Villeurbanne, France.
authors.forename: Gustavo
authors.initials: G
authors.lastname: Sacomoto
authors.affiliation: INRIA Rhône-Alpes, 38330 Montbonnot Saint-Martin, France ; Université de Lyon, 69000 Lyon, France ; Université Lyon 1, Lyon, France ; CNRS, UMR5558, Laboratoire de Biométrie et Biologie Evolutive, 69622 Villeurbanne, France.
authors.forename: Vincent
authors.initials: V
authors.lastname: Lacroix
authors.affiliation: INRIA Rhône-Alpes, 38330 Montbonnot Saint-Martin, France ; Université de Lyon, 69000 Lyon, France ; Université Lyon 1, Lyon, France ; CNRS, UMR5558, Laboratoire de Biométrie et Biologie Evolutive, 69622 Villeurbanne, France.
authors.forename: Marie-France
authors.initials: MF
authors.lastname: Sagot
keywords: Alternative splicing; Bubbles; De Bruijn graphs; Enumeration algorithms; RNA-seq