RAFFT: Efficient prediction of RNA folding pathways using the fast Fourier transform

PLoS Comput Biol. 2022 Aug 26;18(8):e1010448. doi: 10.1371/journal.pcbi.1010448. eCollection 2022 Aug.

Abstract

We propose a novel heuristic to predict RNA secondary structure formation pathways that has two components: (i) a folding algorithm and (ii) a kinetic ansatz. This heuristic is inspired by the kinetic partitioning mechanism, by which molecules follow alternative folding pathways to their native structure, some much faster than others. Similarly, our algorithm RAFFT starts by generating an ensemble of concurrent folding pathways ending in multiple metastable structures, which is in contrast with traditional thermodynamic approaches that find single structures with minimal free energies. When we constrained the algorithm to predict only 50 structures per sequence, near-native structures were found for RNA molecules of length ≤ 200 nucleotides. Our heuristic has been tested on the coronavirus frameshifting stimulation element (CFSE): an ensemble of 68 distinct structures allowed us to produce complete folding kinetic trajectories, whereas known methods require evaluating millions of sub-optimal structures to achieve this result. Thanks to the fast Fourier transform on which RAFFT (RNA folding Algorithm wih Fast Fourier Transform) is based, these computations are efficient, with complexity [Formula: see text].

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Fourier Analysis
  • Nucleic Acid Conformation
  • RNA Folding*
  • RNA* / genetics
  • Thermodynamics

Substances

  • RNA

Grants and funding

MS is funded by Sofja Kovalevskaja Award endowed by the German Federal Ministry of Education and Research, and by the Human Science Frontier Program Organization through a Young Investigator Award grant RGY0077/2019. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.