Using the fast fourier transform to accelerate the computational search for RNA conformational switches.
Bottom Line:
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/.
View Article:
PubMed Central - PubMed
Affiliation: Biology Department, Boston College, Chestnut Hill, Massachusetts, United States of America.
ABSTRACT
Show MeSH
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/. |
Related In:
Results -
Collection
getmorefigures.php?uid=PMC3526635&req=5
Mentions: As visible from the defining recursions, the algorithmic time complexity of RNAbor is and space complexity is , where is the length of input RNA sequence. In contrast, the time complexity of FFTbor is and space complexity is . Figure 8 displays run time curves for both RNAbor and FFTbor, when the initial structure is taken to be either the empty structure or the minimum free energy (MFE) structure. |
View Article: PubMed Central - PubMed
Affiliation: Biology Department, Boston College, Chestnut Hill, Massachusetts, United States of America.