s'authentifier
version française rss feed

hal-00738927, version 1

Efficient Bubble Enumeration in Directed Graphs

Etienne Birmelé 1, Pierluigi Crescenzi 2, Rui Ferreira 3, Roberto Grossi 3, Vincent Lacroix a4, Andrea Marino 2, Nadia Pisanti 3, Gustavo Sacomoto 4, Marie-France Sagot (Auteur à contacter de préférence) b4

String Processing and Information Retrieval (SPIRE) 7608 (2012) 118-129

Résumé : 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.

  • Domaine : Informatique/Bio-informatique
    Sciences du Vivant/Bio-Informatique, Biologie Systémique
    Informatique/Algorithme et structure de données
 
  • hal-00738927, version 1
  • oai:hal.inria.fr:hal-00738927
  • Contributeur : 
  • Soumis le : Vendredi 5 Octobre 2012, 13:54:03
  • Dernière modification le : Dimanche 11 Août 2013, 19:59:54
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...