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

Related in: MedlinePlus

Output from FFTbor on two randomly selected thiamine pyrophosphate riboswitch (TPP) aptamers, taken from the Rfam database[23]. The -axis represents base pair distance from the minimum free energy structure for each given sequence; the -axis represents Boltzmann probabilities , where  denotes the sum of Boltzmann factors or all secondary structures, whose base pair distance from the MFE structure is exactly . (Left) The 97 nt sequence BX842649.1/277414-277318 appears to have a rugged energy landscape near its minimum free energy structure, with distinct low energy structures that may compete with the MFE structure during the folding process. (Right) The 99 nt sequence, AACY022101973.1/389-487 appears to have a smooth energy landscape near its MFE structure, with no distinct low energy structures to might compete with the MFE structure. Based on the FFTbor output or structural profile near MFE structure , one might expect folding time for the first sequence to increase due to competition from metastable structures, while one might expect the second sequence to have rapid folding time. Computational Monte Carlo folding experiments bear out this fact. Kinfold [15] simulations clearly show that the second sequence folds at least four times more quickly than the first sequence. See text for details. Subfigure A Subfigure B Subfigure C Subfigure D.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3526635&req=5

pone-0050506-g002: Output from FFTbor on two randomly selected thiamine pyrophosphate riboswitch (TPP) aptamers, taken from the Rfam database[23]. The -axis represents base pair distance from the minimum free energy structure for each given sequence; the -axis represents Boltzmann probabilities , where denotes the sum of Boltzmann factors or all secondary structures, whose base pair distance from the MFE structure is exactly . (Left) The 97 nt sequence BX842649.1/277414-277318 appears to have a rugged energy landscape near its minimum free energy structure, with distinct low energy structures that may compete with the MFE structure during the folding process. (Right) The 99 nt sequence, AACY022101973.1/389-487 appears to have a smooth energy landscape near its MFE structure, with no distinct low energy structures to might compete with the MFE structure. Based on the FFTbor output or structural profile near MFE structure , one might expect folding time for the first sequence to increase due to competition from metastable structures, while one might expect the second sequence to have rapid folding time. Computational Monte Carlo folding experiments bear out this fact. Kinfold [15] simulations clearly show that the second sequence folds at least four times more quickly than the first sequence. See text for details. Subfigure A Subfigure B Subfigure C Subfigure D.

Mentions: The output of FFTbor, as shown in Figure 2, is a probability distribution, where the -axis represents the base pair distance from an arbitrary, but fixed secondary structure , and the -axis represents the Boltzmann probability that a secondary structure has base pair distance from . Arguably, this probability distribution is an accurate one-dimensional projection of the rugged, high dimensional energy landscape near structure , of the sort artistically rendered in the well-known energy landscape depicted in Figure 1 of [12]. In the sequel, we may call the FFTbor probability distribution a structural neighbor profile, or simply structural profile. A hypothesis behind theoretical work in biomolecular folding theory in [13] is that kinetic folding slows down as the energy landscape becomes more rugged. This is borne out in our computational experiments for RNA using FFTbor, as reported in Figure 2.


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)

Output from FFTbor on two randomly selected thiamine pyrophosphate riboswitch (TPP) aptamers, taken from the Rfam database[23]. The -axis represents base pair distance from the minimum free energy structure for each given sequence; the -axis represents Boltzmann probabilities , where  denotes the sum of Boltzmann factors or all secondary structures, whose base pair distance from the MFE structure is exactly . (Left) The 97 nt sequence BX842649.1/277414-277318 appears to have a rugged energy landscape near its minimum free energy structure, with distinct low energy structures that may compete with the MFE structure during the folding process. (Right) The 99 nt sequence, AACY022101973.1/389-487 appears to have a smooth energy landscape near its MFE structure, with no distinct low energy structures to might compete with the MFE structure. Based on the FFTbor output or structural profile near MFE structure , one might expect folding time for the first sequence to increase due to competition from metastable structures, while one might expect the second sequence to have rapid folding time. Computational Monte Carlo folding experiments bear out this fact. Kinfold [15] simulations clearly show that the second sequence folds at least four times more quickly than the first sequence. See text for details. Subfigure A Subfigure B Subfigure C Subfigure D.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0050506-g002: Output from FFTbor on two randomly selected thiamine pyrophosphate riboswitch (TPP) aptamers, taken from the Rfam database[23]. The -axis represents base pair distance from the minimum free energy structure for each given sequence; the -axis represents Boltzmann probabilities , where denotes the sum of Boltzmann factors or all secondary structures, whose base pair distance from the MFE structure is exactly . (Left) The 97 nt sequence BX842649.1/277414-277318 appears to have a rugged energy landscape near its minimum free energy structure, with distinct low energy structures that may compete with the MFE structure during the folding process. (Right) The 99 nt sequence, AACY022101973.1/389-487 appears to have a smooth energy landscape near its MFE structure, with no distinct low energy structures to might compete with the MFE structure. Based on the FFTbor output or structural profile near MFE structure , one might expect folding time for the first sequence to increase due to competition from metastable structures, while one might expect the second sequence to have rapid folding time. Computational Monte Carlo folding experiments bear out this fact. Kinfold [15] simulations clearly show that the second sequence folds at least four times more quickly than the first sequence. See text for details. Subfigure A Subfigure B Subfigure C Subfigure D.
Mentions: The output of FFTbor, as shown in Figure 2, is a probability distribution, where the -axis represents the base pair distance from an arbitrary, but fixed secondary structure , and the -axis represents the Boltzmann probability that a secondary structure has base pair distance from . Arguably, this probability distribution is an accurate one-dimensional projection of the rugged, high dimensional energy landscape near structure , of the sort artistically rendered in the well-known energy landscape depicted in Figure 1 of [12]. In the sequel, we may call the FFTbor probability distribution a structural neighbor profile, or simply structural profile. A hypothesis behind theoretical work in biomolecular folding theory in [13] is that kinetic folding slows down as the energy landscape becomes more rugged. This is borne out in our computational experiments for RNA using FFTbor, as reported in Figure 2.

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
Related in: MedlinePlus