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

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2013 Jan 4

PMID 23284639

Citations 12

Authors

Evan Senter

Saad Sheikh

Ivan Dotu

Yann Ponty

Peter Clote

Affiliations

Soon will be listed here.

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

Citing Articles

RintC: fast and accuracy-aware decomposition of distributions of RNA secondary structures with extended logsumexp.

Takizawa H, Iwakiri J, Asai K BMC Bioinformatics. 2020; 21(1):210.

PMID: 32448174 PMC: 7245837. DOI: 10.1186/s12859-020-3535-5.

PATTERNA: transcriptome-wide search for functional RNA elements via structural data signatures.

Ledda M, Aviran S Genome Biol. 2018; 19(1):28.

PMID: 29495968 PMC: 5833111. DOI: 10.1186/s13059-018-1399-z.

RNA folding kinetics using Monte Carlo and Gillespie algorithms.

Clote P, Bayegan A J Math Biol. 2017; 76(5):1195-1227.

PMID: 28780735 DOI: 10.1007/s00285-017-1169-7.

Changes in the Plasticity of HIV-1 Nef RNA during the Evolution of the North American Epidemic.

Manzourolajdad A, Gonzalez M, Spouge J PLoS One. 2016; 11(9):e0163688.

PMID: 27685447 PMC: 5042412. DOI: 10.1371/journal.pone.0163688.

Secondary structural entropy in RNA switch (Riboswitch) identification.

Manzourolajdad A, Arnold J BMC Bioinformatics. 2015; 16:133.

PMID: 25928324 PMC: 4448311. DOI: 10.1186/s12859-015-0523-2.

References

Freyhult E, Moulton V, Gardner P . Predicting RNA structure using mutual information. Appl Bioinformatics. 2005; 4(1):53-9. DOI: 10.2165/00822942-200504010-00006. View

Bengert P, Dandekar T . Riboswitch finder--a tool for identification of riboswitch RNAs. Nucleic Acids Res. 2004; 32(Web Server issue):W154-9. PMC: 441490. DOI: 10.1093/nar/gkh352. View

Waldispuhl J, Devadas S, Berger B, Clote P . Efficient algorithms for probing the RNA mutation landscape. PLoS Comput Biol. 2008; 4(8):e1000124. PMC: 2475669. DOI: 10.1371/journal.pcbi.1000124. View

Bergig O, Barash D, Nudler E, Kedem K . STR2: a structure to string approach for locating G-box riboswitch shapes in pre-selected genes. In Silico Biol. 2005; 4(4):593-604. View

Tucker B, Breaker R . Riboswitches as versatile gene control elements. Curr Opin Struct Biol. 2005; 15(3):342-8. DOI: 10.1016/j.sbi.2005.05.003. View

Ding Y, Lawrence C . A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 2003; 31(24):7280-301. PMC: 297010. DOI: 10.1093/nar/gkg938. View

Clote P, Lou F, Lorenz W . Maximum expected accuracy structural neighbors of an RNA secondary structure. BMC Bioinformatics. 2012; 13 Suppl 5:S6. PMC: 3358666. DOI: 10.1186/1471-2105-13-S5-S6. View

Flamm C, Hofacker I, Maurer-Stroh S, Stadler P, Zehl M . Design of multistable RNA molecules. RNA. 2001; 7(2):254-65. PMC: 1370083. DOI: 10.1017/s1355838201000863. View

Nawrocki E, Kolbe D, Eddy S . Infernal 1.0: inference of RNA alignments. Bioinformatics. 2009; 25(10):1335-7. PMC: 2732312. DOI: 10.1093/bioinformatics/btp157. View

10.

Altschul S, Gish W, Miller W, Myers E, Lipman D . Basic local alignment search tool. J Mol Biol. 1990; 215(3):403-10. DOI: 10.1016/S0022-2836(05)80360-2. View

11.

Gardner P, Daub J, Tate J, Moore B, Osuch I, Griffiths-Jones S . Rfam: Wikipedia, clans and the "decimal" release. Nucleic Acids Res. 2010; 39(Database issue):D141-5. PMC: 3013711. DOI: 10.1093/nar/gkq1129. View

12.

Busch A, Backofen R . INFO-RNA--a fast approach to inverse RNA folding. Bioinformatics. 2006; 22(15):1823-31. DOI: 10.1093/bioinformatics/btl194. View

13.

Singh P, Bandyopadhyay P, Bhattacharya S, Krishnamachari A, Sengupta S . Riboswitch detection using profile hidden Markov models. BMC Bioinformatics. 2009; 10:325. PMC: 2770071. DOI: 10.1186/1471-2105-10-325. View

14.

Serganov A, Yuan Y, Pikovskaya O, Polonskaia A, Malinina L, Phan A . Structural basis for discriminative regulation of gene expression by adenine- and guanine-sensing mRNAs. Chem Biol. 2004; 11(12):1729-41. PMC: 4692365. DOI: 10.1016/j.chembiol.2004.11.018. View

15.

Knight T . Engineering novel life. Mol Syst Biol. 2006; 1:2005.0020. PMC: 1681466. DOI: 10.1038/msb4100028. View

16.

Dotu I, Lorenz W, Van Hentenryck P, Clote P . Computing folding pathways between RNA secondary structures. Nucleic Acids Res. 2010; 38(5):1711-22. PMC: 2836545. DOI: 10.1093/nar/gkp1054. View

17.

Bryngelson J, Onuchic J, Socci N, Wolynes P . Funnels, pathways, and the energy landscape of protein folding: a synthesis. Proteins. 1995; 21(3):167-95. DOI: 10.1002/prot.340210302. View

18.

Mandal M, Breaker R . Adenine riboswitches and gene activation by disruption of a transcription terminator. Nat Struct Mol Biol. 2004; 11(1):29-35. DOI: 10.1038/nsmb710. View

19.

Shetty R, Endy D, Knight Jr T . Engineering BioBrick vectors from BioBrick parts. J Biol Eng. 2008; 2:5. PMC: 2373286. DOI: 10.1186/1754-1611-2-5. View

20.

Hofacker I . Vienna RNA secondary structure server. Nucleic Acids Res. 2003; 31(13):3429-31. PMC: 169005. DOI: 10.1093/nar/gkg599. View