A linear inside-outside algorithm for correcting sequencing errors in structured RNA sequences

Vladimir Reinharz 1 Yann Ponty 2, 3, * Jérôme Waldispühl 4, *
* Auteur correspondant
3 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, X - École polytechnique, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Analysis of the sequence-structure relationship in RNA molecules are essential to evolutionary studies but also to concrete applications such as error-correction methodologies in sequencing technologies. The prohibitive sizes of the mutational and conformational landscapes combined with the volume of data to proceed require e cient algorithms to compute sequence-structure properties. More speci cally, here we aim to calculate which mutations increase the most the likelihood of a sequence to a given structure and RNA family. In this paper, we introduce RNApyro, an e cient linear-time and space inside-outside algorithm that computes exact mutational probabilities under secondary structure and evolutionary constraints given as a multiple sequence alignment with a consensus structure. We develop a scoring scheme combining classical stacking base pair energies to novel isostericity scales, and apply our techniques to correct point-wise errors in 5s rRNA sequences. Our results suggest that RNApyro is a promising algorithm to complement existing tools in the NGS error-correction pipeline.
Type de document :
Communication dans un congrès
RECOMB - 17th Annual International Conference on Research in Computational Molecular Biology - 2013, Apr 2013, Beijing, China. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00766781
Contributeur : Yann Ponty <>
Soumis le : mercredi 19 décembre 2012 - 01:41:30
Dernière modification le : jeudi 12 avril 2018 - 01:48:18
Document(s) archivé(s) le : dimanche 18 décembre 2016 - 05:04:39

Fichiers

main_RECOMB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00766781, version 1

Collections

Citation

Vladimir Reinharz, Yann Ponty, Jérôme Waldispühl. A linear inside-outside algorithm for correcting sequencing errors in structured RNA sequences. RECOMB - 17th Annual International Conference on Research in Computational Molecular Biology - 2013, Apr 2013, Beijing, China. 2013. 〈hal-00766781〉

Partager

Métriques

Consultations de la notice

419

Téléchargements de fichiers

211