Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy: The boustrophedon method

Yann Ponty 1, 2
1 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, 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 : We adapt here a surprising technique, the boustrophedon method, to speed up the sampling of RNA secondary structures from the Boltzmann low-energy ensemble. This technique is simple and its implementation straight-forward, as it only requires a permutation in the order of some operations already performed in the stochastic traceback stage of these algorithms. It nevertheless greatly improves their worst-case complexity from O(n^2) to O(n log(n)), for n the size of the original sequence. Moreover the average-case complexity of the generation is shown to be improved from O(n√n) to O(n log(n)) in an Boltzmann-weighted homopolymer model based on the Nussinov–Jacobson free-energy model. These results are extended to the more realistic Turner free-energy model through experiments performed on both structured (Drosophilia melanogaster mRNA 5S) and hybrid (Staphylococcus aureus RNAIII) RNA sequences, using a boustrophedon modified version of the popular software UnaFold. This improvement allows for the sampling of greater and more significant sets of structures in a given time.
Type de document :
Article dans une revue
Journal of Mathematical Biology, Springer Verlag (Germany), 2008, 56 (1-2), pp.107--127. 〈10.1007/s00285-007-0137-z〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00548863
Contributeur : Yann Ponty <>
Soumis le : lundi 20 décembre 2010 - 16:44:16
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08

Identifiants

Citation

Yann Ponty. Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy: The boustrophedon method. Journal of Mathematical Biology, Springer Verlag (Germany), 2008, 56 (1-2), pp.107--127. 〈10.1007/s00285-007-0137-z〉. 〈inria-00548863〉

Partager

Métriques

Consultations de la notice

137