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, *
* Corresponding author
1 Department of Biology
2 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
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
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 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/
Document type :
Journal articles
Complete list of metadatas
https://hal.inria.fr/hal-00769740
Contributor : Yann Ponty <>
Submitted on : Thursday, January 3, 2013 - 10:05:00 AM
Last modification on : Tuesday, May 21, 2019 - 2:48:52 PM

Links full text

openaccess

Identifiers

Collections

INRIA | LIX | X | PARISTECH | X-LIX | UMR8623 | X-DEP-INFO

Citation

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, Public Library of Science, 2012, 7 (12), pp.e50506. ⟨10.1371/journal.pone.0050506⟩. ⟨hal-00769740⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

376

Contact


archive-ouverte@inria.fr