Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy: the boustrophedon method.
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(n2)] 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 square root 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.
Ponty
Yann
Y
Biology Department, Higgins Hall 577, Boston College, 140 Commonwealth Avenue, Chestnut Hill, MA 02467, USA. ponty@bc.edu
D000465:Algorithms; D000818:Animals; D001426:Bacterial Proteins / Q000235:genetics; D019295:Computational Biology / Q000379:methods*; D004331:Drosophila melanogaster / Q000235:genetics; D008956:Models, Chemical; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D012341:RNA, Ribosomal, 5S / Q000235:genetics; D013211:Staphylococcus aureus; D013816:Thermodynamics; D015534:Trans-Activators / Q000235:genetics
C095698:Agr protein, Staphylococcus aureus; D001426:Bacterial Proteins; D012341:RNA, Ribosomal, 5S; D015534:Trans-Activators; D012313:RNA