A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs and its application to the detection of alternative splicing in RNA-seq data

Gustavo Akio Tominaga Sacomoto 1 Vincent Lacroix 1 Marie-France Sagot 1, *
* Auteur correspondant
1 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive
Abstract : We present a new algorithm for enumerating bubbles with length constraints in directed graphs. This problem arises in transcriptomics, where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq. This is the fi rst polynomial-delay algorithm for this problem and we show that in practice, it is faster than previous approaches. This enables us to deal with larger instances and therefore to discover novel alternative splicing events, especially long ones, that were previously overseen using existing methods.
Type de document :
Communication dans un congrès
Workshop on Algorithms in Bioinformatics (WABI), Sep 2013, Nice, France. Springer-Verlag, 2013, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-00842982
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 10 juillet 2013 - 07:05:20
Dernière modification le : vendredi 20 avril 2018 - 01:27:43

Identifiants

  • HAL Id : hal-00842982, version 1

Collections

Citation

Gustavo Akio Tominaga Sacomoto, Vincent Lacroix, Marie-France Sagot. A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs and its application to the detection of alternative splicing in RNA-seq data. Workshop on Algorithms in Bioinformatics (WABI), Sep 2013, Nice, France. Springer-Verlag, 2013, Lecture Notes in Computer Science. 〈hal-00842982〉

Partager

Métriques

Consultations de la notice

259