Limits...
Using the fast fourier transform to accelerate the computational search for RNA conformational switches.

Senter E, Sheikh S, Dotu I, Ponty Y, Clote P - PLoS ONE (2012)

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

Show MeSH
Run times in seconds for RNAbor and FFTbor, on random RNA of length  in step size of 20 nt. Each algorithm was run with the empty initial structure , see rows RNAbor (empty), FFTbor (empty), and with the minimum free energy structure as the initial structure , see rows RNAbor (MFE) and FFTbor (MFE). Note that for both RNAbor and FFTbor, the run time increases when  is the MFE structure, rather than the empty structure. Notice the radical improvement in the run time of FFTbor over that of RNAbor.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3526635&req=5

pone-0050506-g008: Run times in seconds for RNAbor and FFTbor, on random RNA of length in step size of 20 nt. Each algorithm was run with the empty initial structure , see rows RNAbor (empty), FFTbor (empty), and with the minimum free energy structure as the initial structure , see rows RNAbor (MFE) and FFTbor (MFE). Note that for both RNAbor and FFTbor, the run time increases when is the MFE structure, rather than the empty structure. Notice the radical improvement in the run time of FFTbor over that of RNAbor.

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.


Using the fast fourier transform to accelerate the computational search for RNA conformational switches.

Senter E, Sheikh S, Dotu I, Ponty Y, Clote P - PLoS ONE (2012)

Run times in seconds for RNAbor and FFTbor, on random RNA of length  in step size of 20 nt. Each algorithm was run with the empty initial structure , see rows RNAbor (empty), FFTbor (empty), and with the minimum free energy structure as the initial structure , see rows RNAbor (MFE) and FFTbor (MFE). Note that for both RNAbor and FFTbor, the run time increases when  is the MFE structure, rather than the empty structure. Notice the radical improvement in the run time of FFTbor over that of RNAbor.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3526635&req=5

pone-0050506-g008: Run times in seconds for RNAbor and FFTbor, on random RNA of length in step size of 20 nt. Each algorithm was run with the empty initial structure , see rows RNAbor (empty), FFTbor (empty), and with the minimum free energy structure as the initial structure , see rows RNAbor (MFE) and FFTbor (MFE). Note that for both RNAbor and FFTbor, the run time increases when is the MFE structure, rather than the empty structure. Notice the radical improvement in the run time of FFTbor over that of RNAbor.
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.

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

Show MeSH