The main challenge in de novo assembly of NGS data is certainly to deal with repeats that are longer than the reads. This is particularly true for RNA-seq data, since coverage information cannot be used to flag repeated sequences, of which transposable elements are one of the main examples. Most transcriptome assemblers are based on de Bruijn graphs and have no clear and explicit model for repeats in RNA-seq data, relying instead on heuristics to deal with them. The results of this work are twofold. First, we introduce a formal model for representing high copy-number repeats in RNA-seq data and exploit its properties to infer a combinatorial characteristic of repeat-associated subgraphs. We show that the problem of identifying in a de Bruijn graph a subgraph with this characteristic is NP-complete. In a second step, we show that in the specific case of a local assembly of alternative splicing (AS) events, using our combinatorial characterization we can implicitly avoid such subgraphs. In particular, we designed and implemented an algorithm to efficiently identify AS events that are not included in repeated regions. Finally, we validate our results using synthetic data. We also give an indication of the usefulness of our method on real data. © 2014 Springer-Verlag Berlin Heidelberg.

Navigating in a sea of repeats in RNA-seq without drowning / Sacomoto, G.; Sinaimeri, Blerina; Marchet, C.; Miele, V.; Sagot, M. -F.; Lacroix, V.. - Algorithms in Bioinformatics, (2014), pp. 82-96. (14th International Workshop on Algorithms in Bioinformatics, WABI 2014, Wroclaw, Poland, September 8-10, 2014). [10.1007/978-3-662-44753-6_7].

Navigating in a sea of repeats in RNA-seq without drowning

Sinaimeri B.;
2014

Abstract

The main challenge in de novo assembly of NGS data is certainly to deal with repeats that are longer than the reads. This is particularly true for RNA-seq data, since coverage information cannot be used to flag repeated sequences, of which transposable elements are one of the main examples. Most transcriptome assemblers are based on de Bruijn graphs and have no clear and explicit model for repeats in RNA-seq data, relying instead on heuristics to deal with them. The results of this work are twofold. First, we introduce a formal model for representing high copy-number repeats in RNA-seq data and exploit its properties to infer a combinatorial characteristic of repeat-associated subgraphs. We show that the problem of identifying in a de Bruijn graph a subgraph with this characteristic is NP-complete. In a second step, we show that in the specific case of a local assembly of alternative splicing (AS) events, using our combinatorial characterization we can implicitly avoid such subgraphs. In particular, we designed and implemented an algorithm to efficiently identify AS events that are not included in repeated regions. Finally, we validate our results using synthetic data. We also give an indication of the usefulness of our method on real data. © 2014 Springer-Verlag Berlin Heidelberg.
2014
978-3-662-44752-9
978-3-662-44753-6
Alternative Splice, Transposable Element, Directed Graph, Recursive Call, Alternative Splice Event
File in questo prodotto:
File Dimensione Formato  
wabi_sinaimeri.pdf

Solo gestori archivio

Tipologia: Documento in Pre-print
Licenza: DRM (Digital rights management) non definiti
Dimensione 684.36 kB
Formato Adobe PDF
684.36 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202529
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact