Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy |
| |
Authors: | Yann Ponty |
| |
Affiliation: | (1) Biology Department, Higgins Hall 577, Boston College, 140 Commonwealth Avenue, Chestnut Hill, MA 02467, USA |
| |
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 to , for n the size of the original sequence. Moreover the average-case complexity of the generation is shown to be improved from to 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. |
| |
Keywords: | Statistical sampling Boltzmann free-energy ensemble RNA structure MFE folding |
本文献已被 PubMed SpringerLink 等数据库收录! |
|