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 transcrip‑ tomics 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. Conclusion: 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.
Type de document :
Article dans une revue
Algorithms for Molecular Biology, BioMed Central, 2015, pp.10. 〈10.1186/s13015-015-0046-4〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01170399
Contributeur : Marie-France Sagot <>
Soumis le : mardi 20 octobre 2015 - 14:26:22
Dernière modification le : mardi 16 janvier 2018 - 15:45:46
Document(s) archivé(s) le : jeudi 21 janvier 2016 - 10:17:20

Fichier

Sacomoto2015.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Gustavo Sacomoto, Vincent Lacroix, Marie‑france Sagot. A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs. Algorithms for Molecular Biology, BioMed Central, 2015, pp.10. 〈10.1186/s13015-015-0046-4〉. 〈hal-01170399〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

59