Skip to Main content Skip to Navigation
New interface

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

Gustavo Akio Tominaga Sacomoto 1 
1 Baobab
PEGASE - Département PEGASE [LBBE]
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
Document type :
Complete list of metadata

Cited literature [150 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, February 20, 2018 - 1:35:09 PM
Last modification on : Tuesday, October 18, 2022 - 4:22:46 AM
Long-term archiving on: : Monday, May 21, 2018 - 12:56:40 PM


Files produced by the author(s)


  • HAL Id : tel-01095280, version 2



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⟩



Record views


Files downloads