Efficient algorithms for de novo assembly of alternative splicing events from RNA-seq data

Résumé : Dans cette thèse, nous abordons le problème de l'identification et de la quantification de variants (épissage alternatif et polymorphisme génomique) dans des données de RNA-seq sans génome de référence, et sans faire un assemblage complet des transcripts. Basé sur l'idée que chaque variant correspond à un motif reconnaissable, qu'on appelle une bulle, dans un graphe de Bruijn construit à partir des lectures de RNA-seq, nous proposons un modèle pour les variants dans de tels graphes. Nous introduisons ensuite une méthode, appelé KisSplice, pour extraire les événements d'épissage alternatif, et nous montrons qu'il trouve plus d'événements corrects que les assembleurs de transcriptome traditionnels. Afin d'améliorer son temps d'exécution, nous proposons un nouvel algorithme polynomial pour énumérer les bulles. On montre qu'il est plusieurs ordres de grandeur plus rapide que les approches précédentes. Afin de réduire sa consommation en mémoire, nous proposons une nouvelle façon de représenter un graphe de Bruijn. Nous montrons que notre approche utilise 30% à 40% moins de mémoire que l'état de l'art. Nous appliquons les techniques développées pour énumérer les bulles à deux problémes classiques. Nous donnons le premier algorithme optimal pour énumérer les cycles dans des graphes non orientés. Il s'agit de la première amélioration à ce probléme en près de 40 ans. Nous considérons ensuite une variante du problème des K chemins plus courts: au lieu de limiter le nombre des chemins, nous limitons leurs poids. Nous présentons de nouveaux algorithmes qui utilisent exponentiellement moins mémoire que les approches précédentes
Type de document :
Thèse
Quantitative Methods [q-bio.QM]. Université Claude Bernard - Lyon I, 2014. English. 〈NNT : 2014LYO10043〉
Liste complète des métadonnées

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

https://hal.inria.fr/tel-01095280
Contributeur : Abes Star <>
Soumis le : mardi 20 février 2018 - 13:35:09
Dernière modification le : jeudi 19 avril 2018 - 14:49:46

Fichier

TH2014_Tominaga-Sacomoto_Gusta...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01095280, version 2

Collections

Citation

Gustavo Akio Tominaga Sacomoto. Efficient algorithms for de novo assembly of alternative splicing events from RNA-seq data. Quantitative Methods [q-bio.QM]. Université Claude Bernard - Lyon I, 2014. English. 〈NNT : 2014LYO10043〉. 〈tel-01095280v2〉

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

13