title: Using structural and evolutionary information to detect and correct pyrosequencing errors in noncoding RNAs.
abstract: The analysis of the sequence-structure relationship in RNA molecules is not only essential for evolutionary studies but also for concrete applications such as error-correction in next generation sequencing (NGS) technologies. The prohibitive sizes of the mutational and conformational landscapes, combined with the volume of data to process, require efficient algorithms to compute sequence-structure properties. In this article, we address the correction of NGS errors by calculating which mutations most increase the likelihood of a sequence to a given structure and RNA family. We introduce RNApyro, an efficient, 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 scores and apply our techniques to correct pointwise errors in 5s and 16s rRNA sequences. Our results suggest that RNApyro is a promising algorithm to complement existing tools in the NGS error-correction pipeline.
authors.affiliation: 1 School of Computer Science, McGill University , Montreal, Canada .
authors.forename: Vladimir
authors.initials: V
authors.lastname: Reinharz
authors.forename: Yann
authors.initials: Y
authors.lastname: Ponty
authors.forename: Jérôme
authors.initials: J
authors.lastname: Waldispühl
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D019143:Evolution, Molecular; D059014:High-Throughput Nucleotide Sequencing; D006801:Humans; D008957:Models, Genetic; D009690:Nucleic Acid Conformation; D012329:RNA, Bacterial / Q000235:genetics; D012336:RNA, Ribosomal, 16S / Q000235:genetics*; D012341:RNA, Ribosomal, 5S / Q000235:genetics*; D022661:RNA, Untranslated / Q000235:genetics*; D012372:ROC Curve; D017423:Sequence Analysis, RNA
chemical_list: D012329:RNA, Bacterial; D012336:RNA, Ribosomal, 16S; D012341:RNA, Ribosomal, 5S; D022661:RNA, Untranslated