the variety of biochemical functions that are being carried out by rna molecules is mesmerizing .
many rnas such as ribosomal rna , rnaase p or trna attain a defined secondary and tertiary structure that is vital to their function .
experimentally determined structures are only available for a small fraction of rnas that are of interest .
this makes the computational prediction of the base - pairing pattern ( the secondary structure ) of rna an important problem .
one major breakthrough was the development of dynamic programming algorithms that could predict the minimum free energy secondary structure of rna sequence assuming that the structures are non - nested ( 15 ) .
subsequently , dynamic programming algorithms have been extended to allow certain classes of pseudoknots ( 6,7 ) .
many rna secondary structure prediction algorithms ( including the one presented here ) are based on the idea of iteratively adding substructures to an initially unfolded sequence ( 8,9 ) .
genetic algorithms are an example of such algorithms and have proven very useful for exploring pseudoknotted structures and sub - optimal rna structures ( 1014 ) . allowing pseudoknots is desirable simply because rna structures determined by x - ray crystallography or nmr revealed that many rnas contain non - nested base pairing interactions . allowing all possible base pairing interactions
leads to the potential problem for structure prediction approaches that not only are there many more conformations to consider , but also many conformations are not sterically feasible . here
, we describe a computational approach for rna secondary structure prediction that has no restriction in terms of pseudoknot complexity , but additionally checks the steric feasibility of the considered conformations .
the described approach of rna secondary structure prediction is based on the idea of maximizing matching helices in a secondary structure ( 10 ) . a flow chart of the algorithm is shown in figure 1 .
briefly , the method works as follows : initially , a list ( called a stem - list ) of all possible helices with more than 3 bp is generated .
the secondary structure prediction is performed by picking the best - scoring structure obtained after 50 folding simulation runs .
the score is set to be the sum of the free energy contribution of the already placed helices .
each folding simulation run is performed by picking helices from the stem list with a boltzmann - weighted probability .
estimating the free energy contribution of an rna double - helix is accomplished using the rna vienna package ( 2 ) .
each chosen helix is represented by a very coarse - grained 3d representation in a virtual 3d workspace .
an rna double helix is represented by a cylinder ( using a radius of 6.5  and a length of 2.7  times the number of base pairs ) that is capped with a half - sphere on both ends .
this shape is called a capsule . a schematic diagram of the mapping of an rna secondary structure into a highly coarse - grained 3d representation is shown in figure 2 .
the main reason for choosing capped cylinders over regular cylinders is the computational efficiency of collision detection .
single stranded regions between helices are represented as constraints for the maximum distance between the ends of the capped cylinders .
a newly chosen capped cylinder is placed into the 3d simulation space at a random position such that the distance - constraints are fulfilled .
the distance constraints are a function of the single - stranded sequence lengths between connected helices .
the maximum distance between helix ends is 2.0  + n*8.0  with n being the sequence separation .
figure 2.scheme for mapping between an rna secondary structure ( a ) and the used 3d coarse - grained representation ( b ) .
only those rna secondary structures can be a ( partial ) solution of a secondary structure prediction , for which the algorithm succeeds in placing the corresponding capped cylinders such that they do not collide and do not violate distance constraints . a flow - chart depicting the algorithm for predicting rna secondary structures .
scheme for mapping between an rna secondary structure ( a ) and the used 3d coarse - grained representation ( b ) .
only those rna secondary structures can be a ( partial ) solution of a secondary structure prediction , for which the algorithm succeeds in placing the corresponding capped cylinders such that they do not collide and do not violate distance constraints .
if cylinders collide , the newly placed capped cylinder is placed at a different random position .
if after 20 attempts the newly placed capped cylinder is still colliding with previously placed capped cylinders , the positions of all capped cylinders are optimized in order to minimize collisions and constraint violations .
if no collision - free position can be found , the newly chosen helix and its capped cylinder representation is discarded .
helices that are part of the stem - list and that share bases with the newly placed helix are removed from the stem - list . in the next iteration
the next helix is chosen until no more helices can be placed . once no more
fifty simulation runs are performed and the overall best - scoring structure is returned to the user .
the web server has been implemented using the grails framework ( 18 ) , which is based on the groovy programming language . for a secondary structure prediction request ,
the web server launches the cylofold binary on a linux compute cluster . after the prediction result has been generated , the program varna ( 19 )
a user of the cylofold prediction web server can start a secondary structure prediction request by entering (  pasting ) a nucleotide sequence ( as raw characters or in fasta form , both acgu and acgt alphabets are accepted ) into the web form and pressing 
submit. the maximum sequence length that is currently accepted by the web server is 300 nt .
the initial return of the web server is a unique i d , which is needed if one wants to access results at a later time . due to the compute - intensive approach for the prediction
, it can take several minutes for the server to finalize a secondary structure prediction .
the user can access the results by one of three methods : a simple  reload of the initial result page will update the status of the prediction and will eventually contain the prediction results . alternatively , the user can bookmark the initial result page in the web browser and return to it at a later time .
lastly , the unique i d provided after submitting the secondary structure prediction compute request can be used to access the results using another web form available on the server home page . a typical output from a completed rna structure prediction
the prediction result is presented to the user in three different formats : ( i ) an image of the predicted rna secondary structure created by varna ( 19 ) ; ( ii ) an extended bracket notation in which nested base pairs are denoted as pairs of nested parentheses and helices corresponding to pseudoknot interactions are denoted as letters ; ( iii ) the 
ct file format that is also generated by other programs such as mfold ( 5 ) .
this format contains a list of the indices of the bases and their predicted base - pairing partners . 

the shown sequence corresponds to the bacteriophage t2 gene 32 mrna pseudoknot ( pdb 2tpk ) .
the shown sequence corresponds to the bacteriophage t2 gene 32 mrna pseudoknot ( pdb 2tpk ) .
a user of the cylofold prediction web server can start a secondary structure prediction request by entering (  pasting ) a nucleotide sequence ( as raw characters or in fasta form , both acgu and acgt alphabets are accepted ) into the web form and pressing 
submit. the maximum sequence length that is currently accepted by the web server is 300 nt .
the initial return of the web server is a unique i d , which is needed if one wants to access results at a later time . due to the compute - intensive approach for the prediction
, it can take several minutes for the server to finalize a secondary structure prediction .
the user can access the results by one of three methods : a simple  reload of the initial result page will update the status of the prediction and will eventually contain the prediction results . alternatively , the user can bookmark the initial result page in the web browser and return to it at a later time .
lastly , the unique i d provided after submitting the secondary structure prediction compute request can be used to access the results using another web form available on the server home page . a typical output from a completed rna structure prediction
the prediction result is presented to the user in three different formats : ( i ) an image of the predicted rna secondary structure created by varna ( 19 ) ; ( ii ) an extended bracket notation in which nested base pairs are denoted as pairs of nested parentheses and helices corresponding to pseudoknot interactions are denoted as letters ; ( iii ) the
 ct file format that is also generated by other programs such as mfold ( 5 ) .
this format contains a list of the indices of the bases and their predicted base - pairing partners . 

the shown sequence corresponds to the bacteriophage t2 gene 32 mrna pseudoknot ( pdb 2tpk ) .
the shown sequence corresponds to the bacteriophage t2 gene 32 mrna pseudoknot ( pdb 2tpk ) .
the performance of the new rna secondary structure prediction method was evaluated using two different data sets .
data set 1 ( corresponding to the results shown in table 1 ) consists of 26 rna sequences , whose tertiary structure is available in the protein data bank ( pdb ) .
the reference secondary structure was obtained by extracting the base pair information from the pdb coordinate file using the program rnaview ( 20 ) .
data set 2 consists of 241 rna sequences and secondary structures originating from pseudobase ( 21,22 ) . 

table 1.prediction results corresponding to 26 rna structures that are available in the protein dank bankpdbdescriptionlpkfcfpkhkufmccsnsppvmccsnsppvmccsnsppvmccsnsppv1a60tymv trna - like structure4413.60.740.770.710.961.000.930.830.770.910.830.770.911cx0hdv ribozyme7222.20.010.000.000.010.000.000.010.000.000.010.000.001e95srv-1 pseudoknot3633.31.001.001.001.001.001.001.001.001.000.700.501.001hvuhiv rt bind .
intron700.00.910.870.950.810.830.790.810.830.790.960.960.961l2xviral rna pseudoknot2722.20.941.000.890.941.000.890.790.631.000.790.631.001q9a23s rrna sarcin / ricin270.00.910.831.000.770.830.710.861.000.750.770.830.711u8dguanine riboswitch6711.90.870.870.870.880.781.000.880.781.000.880.781.002a43luteoviral pseudoknot2623.00.931.000.880.931.000.880.750.571.000.750.571.002g1wtmrna pseudoknot2218.10.811.000.670.861.000.750.810.671.000.810.671.002gissam- riboswitch948.50.800.760.850.800.760.850.860.860.860.550.550.552hoothi - box riboswitch830.00.700.670.740.580.620.540.580.620.540.580.620.542k95p2b - p3 telo - merase rna4837.50.890.801.000.890.801.000.750.80.710.540.400.752oiul1 ribozyme ligase adduct710.00.860.780.950.980.961.000.980.961.000.981.001.002qushammerhead ribozyme682.90.950.911.000.950.911.000.950.911.000.951.001.002qwysam - ii riboswitch5226.90.480.460.500.480.460.50.340.310.40.350.310.402rp0pemv1 mrna pseudoknot2615.30.881.000.780.881.000.780.840.711.000.840.711.002tpkt2 gene 32 mrna p.k.3627.71.001.001.001.001.001.000.710.580.880.630.580.70361ddomain e of 5s rrna190.00.861.000.750.861.000.750.830.830.830.830.830.833diglysine riboswitch17330.10.890.850.930.740.720.760.740.720.760.740.720.763fu2class - i preq1 riboswitch3218.80.790.631.000.790.631.000.790.631.000.790.631.003phptymv p.k .
frame - shifting p.k.2722.20.941.000.890.941.000.890.790.631.000.790.631.00meanall0.830.850.830.820.840.810.750.710.830.730.650.83meanno pseudoknots<5.00.870.850.890.810.840.800.820.840.810.870.900.87meanpseudoknots>5.00.810.840.800.820.840.820.730.650.840.660.550.80l , sequence length ; pkf , fraction of pseudoknot interactions ; for each of the four different prediction methods ( cf , cylofold ; pk , pknotsrg ; hk , hotknots 2.0 ; uf , unafold ) we report three different measures of prediction quality ( sns , sensitivity ; ppv , positive predictive value ) .
prediction results corresponding to 26 rna structures that are available in the protein dank bank l , sequence length ; pkf , fraction of pseudoknot interactions ; for each of the four different prediction methods ( cf , cylofold ; pk , pknotsrg ; hk , hotknots 2.0 ; uf , unafold ) we report three different measures of prediction quality ( sns , sensitivity ; ppv , positive predictive value ) . in order to quantify the time - complexity of the folding method , we fitted a function of the form a*n ( with n being the number of residues in the input sequence ) to the execution time needed for the cases of the 241 sequence set .
we found that the execution time ( measured in seconds ) of the structure prediction is well described by the function 2.74 * 10*n .
the timing evaluation was performed on a computer with 4 gb of ram and an intel 64-bit xeon processor ( 3.0mhz ) .
we report in tables 1 and 2 prediction results for these two data sets together with the corresponding results obtained by running the rna secondary structure prediction programs hotknots 2.0 ( 8) , pknotsrg ( 7 ) and unafold ( 23 ) . 

table 2.prediction results for a set of 241 rna sequences that are part of pseudobase for the programs cylofold , pknotsrg ( 7 ) , hotknots 2.0 ( 8) and unafold ( 23)mccsnsppvcylofold0.7520.7630.747pknotsrg0.7480.7530.756hotknots 2.00.6110.5650.684unafold0.5970.5320.692sns , sensitivity of predicted base pairs ; ppv , positive predictive value .
prediction results for a set of 241 rna sequences that are part of pseudobase for the programs cylofold , pknotsrg ( 7 ) , hotknots 2.0 ( 8) and unafold ( 23 ) sns , sensitivity of predicted base pairs ; ppv , positive predictive value .
the average matthews correlation coefficient ( mcc ) obtained by comparing the base pairing pattern of the predicted secondary structures with their respective reference secondary structure is for data set 1 and cylofold 0.83 ; this can be compared to pknotsrg ( 0.82 ) , hotknots 2.0 ( 0.75 ) and unafold ( 0.73 ) ( see row of table 1 named
we divided this data set into two subsets according to the fraction of pseudoknot base pairs in the respective structures .
the eight pdb structures with < 5% pseudoknotted base pairs correspond to an average mcc of 0.87 for cylofold compared to 0.81 for pknotsrg , 0.82 for hotknots 2.0 and 0.87 for unafold .
the 18 structures listed in table 1 that have a pseudoknot amount > 5% correspond to an average mcc of 0.81 for cylofold , 0.82 for pknotsrg , 0.73 for hotknots 2.0 and 0.66 for unafold . using the larger data set 2 , one obtains an average mcc of 0.752 for cylofold and 0.748 for pknotsrg
one can see the rna secondary structure predictions obtained by cylofold correspond to the highest mcc ( compared to the programs pknotsrg , hotknots 2.0 and unafold ) .
it also has the highest average base pair prediction sensitivity ( 0.763 ) . for another measure , the positive predictive value ( how often are predicted base pairs part of the reference secondary structure )
, all programs obtain averages between 0.68 and 0.76 for data set 2 with pknotsrg leading with a value of 0.756 .
it should be noted that the mcc is often used as an overall measure of prediction quality , while sensitivity , specificity and positive predictive value capture certain other aspects of the prediction quality .
the key advantage of cylofold is that there is no restriction in terms of the classes of pseudoknots that are being considered .
also , it should be noted that the employed model of simulated rna folding by placing helices with a probability according to their free energy contribution is in essence very simple ( 24 ) . in that sense
it is surprising how well the method performs , and it should be an encouragement to continue to develop rna folding algorithms that are substantially different from established approaches .
we show using two different data sets that the prediction accuracy ( mcc ) is comparable to the rna secondary structure prediction program pknotsrg .
another novel aspect is that at each step during the simulated folding process , the steric feasibility of the predicted structures is checked for steric feasibility using a highly coarse - grained 3d representation .
the method is made available in the form of a user - friendly web server .
this project has been funded in whole or in part with federal funds from the national cancer institute , national institutes of health , under contract hhsn26120080001e .
this research was supported by the intramural research program of the nih , national cancer institute , center for cancer research .
 computational rna secondary structure prediction approaches differ by the way rna pseudoknot interactions are handled . for reasons of computational efficiency , most approaches only allow a limited class of pseudoknot interactions or are not considering them at all . here 
 we present a computational method for rna secondary structure prediction that is not restricted in terms of pseudoknot complexity . 
 the approach is based on simulating a folding process in a coarse - grained manner by choosing helices based on established energy rules . 
 the steric feasibility of the chosen set of helices is checked during the folding process using a highly coarse - grained 3d model of the rna structures . using two data sets of 26 and 241 rna sequences 
 we find that this approach is competitive compared to the existing rna secondary structure prediction programs pknotsrg , hotknots and unafold . 
 the key advantages of the new method are that there is no algorithmic restriction in terms of pseudoknot complexity and a test is made for steric feasibility . 
 availability : the program is available as web server at the site : http://cylofold.abcc.ncifcrf.gov . 
INTRODUCTION
ALGORITHM
IMPLEMENTATION
Usage
RESULTS AND DISCUSSION
CONCLUSION
FUNDING