Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches

Evan Senter (1) , Saad Sheikh (2) , Ivan Dotu (1) , Yann Ponty (3, 4) , Peter Clote (1)

1 Department of Biology
2 UF|CISE - Department of Computer and Information Science and Engineering [Gainesville]
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
4 AMIB - Algorithms and Models for Integrative Biology

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 k 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/

Evan Senter, Saad Sheikh, Ivan Dotu, Yann Ponty, Peter Clote. Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches. PLoS ONE, 2012, 7 (12), pp.e50506. ⟨10.1371/journal.pone.0050506⟩. ⟨hal-00769740⟩