Efficient algorithms for de novo assembly of alternative splicing events from RNA-seq data / Gustavo Akio Tominaga Sacomoto ; sous la direction de Marie-France Sagot et de Pierluigi Crescenzi et de Vincent Lacroix

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Algorithmes

Structures de données (informatique)

Épissage alternatif

Analyse combinatoire énumérative

Classification Dewey : 572.8

Sagot, Marie-France (1956-....) (Directeur de thèse / thesis advisor)

Crescenzi, Pierluigi (1961-....) (Directeur de thèse / thesis advisor)

Lacroix, Vincent (1981-....) (Directeur de thèse / thesis advisor)

Brochier-Armanet, Céline (Président du jury de soutenance / praeses)

Brudno, Michael (19..-....) (Rapporteur de la thèse / thesis reporter)

Guigo, Roderic (Rapporteur de la thèse / thesis reporter)

Widmayer, Peter (1953-....) (Rapporteur de la thèse / thesis reporter)

Lecroq, Thierry (1965-.... ; enseignant-chercheur en informatique) (Membre du jury / opponent)

Université Claude Bernard (Lyon) (Organisme de soutenance / degree-grantor)

École Doctorale Evolution Ecosystèmes Microbiologie Modélisation (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire de Biométrie et Biologie Evolutive (Laboratoire associé à la thèse / thesis associated laboratory)

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

Résumé / Abstract : In this thesis, we address the problem of identifying and quantifying variants (alternative splicing and genomic polymorphism) in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the idea that each variant corresponds to a recognizable pattern, a bubble, in a de Bruijn graph constructed from the RNA-seq reads, we propose a general model for all variants in such graphs. We then introduce an exact method, called KisSplice, to extract alternative splicing events and show that it outperforms general purpose transcriptome assemblers. We put an extra effort to make KisSplice as scalable as possible. In order to improve the running time, we propose a new polynomial delay algorithm to enumerate bubbles. We show that it is several orders of magnitude faster than previous approaches. In order to reduce its memory consumption, we propose a new compact way to build and represent a de Bruijn graph. We show that our approach uses 30% to 40% less memory than the state of the art, with an insignificant impact on the construction time. Additionally, we apply the techniques developed to list bubbles in two classical problems: cycle enumeration and the K-shortest paths problem. We give the first optimal algorithm to list cycles in undirected graphs, improving over Johnson’s algorithm. This is the first improvement to this problem in almost 40 years. We then consider a different parameterization of the K-shortest (simple) paths problem: instead of bounding the number of st-paths, we bound the weight of the st-paths. We present new algorithms using exponentially less memory than previous approaches