Using the fast fourier transform to accelerate the computational search for RNA conformational switches

PLoS One. 2012;7(12):e50506. doi: 10.1371/journal.pone.0050506. Epub 2012 Dec 19.

Abstract

Using complex roots of unity and the Fast Fourier Transform, we design a new thermodynamics-based algorithm, FFTbor, that computes the Boltzmann probability that secondary structures differ by [Formula: see text] base pairs from an arbitrary initial structure of a given RNA sequence. The algorithm, which runs in quartic time O(n(4)) and quadratic space O(n(2)), is used to determine the correlation between kinetic folding speed and the ruggedness of the energy landscape, and to predict the location of riboswitch expression platform candidates. A web server is available at http://bioinformatics.bc.edu/clotelab/FFTbor/.

Publication types

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

MeSH terms

  • Algorithms
  • Base Sequence
  • Computational Biology / methods*
  • Escherichia coli K12 / enzymology
  • Fourier Analysis*
  • Nucleic Acid Conformation*
  • Operon / genetics
  • Phenylalanine-tRNA Ligase / genetics
  • RNA / chemistry*
  • RNA / genetics
  • Time Factors

Substances

  • RNA
  • Phenylalanine-tRNA Ligase

Grants and funding

Source of funding provided by National Science Foundation grants DMS-1016618 and DMS-0817971 to PC, www.nsf.gov. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.