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

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 [Image: see text] base pairs from an arbitrary initial structure of a given RNA sequence. The algorithm, which runs in quartic time [Image: see text] and quadratic space [Image: see text], 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/.