W368–W372 Nucleic Acids Research, 2010, Vol. 38, Web Server issue doi:10.1093/nar/gkq432 Published online 25 May 2010 CyloFold: secondary structure prediction including pseudoknots Eckart Bindewald1, Tanner Kluth2 and Bruce A. Shapiro2,* 1Basic Science Program, SAIC-Frederick, Inc., NCI-Frederick, Frederick, MD 21702 and 2Center for Cancer Research Nanobiology Program, NCI-Frederick, Frederick, MD 21702, USA Received February 24, 2010; Revised April 23, 2010; Accepted May 6, 2010 ABSTRACT Computational RNA secondary structure prediction approaches differ by the way RNA pseudoknot inter- actions are handled. For reasons of computational efficiency, most approaches only allow a limited class of pseudoknot interactions or are not con- sidering them at all. Here we present a computation- al method for RNA secondary structure prediction that is not restricted in terms of pseudoknot com- plexity. 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 com- petitive 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 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 deﬁned 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 break- through 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 (1–5). 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 struc- tures (10–14). 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 inter- actions leads to the potential problem for structure pre- diction approaches that not only are there many more conformations to consider, but also many conformations are not sterically feasible. Here, we describe a computa- tional 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. ALGORITHM The described approach of RNA secondary structure pre- diction is based on the idea of maximizing matching helices in a secondary structure (10). A ﬂow chart of the algorithm is shown in Figure 1. Brieﬂy, the method works as follows: Initially, a list (called a stem-list) of all possible helices with more than 3 bp is generated. Helices can contain Watson–Crick and GU–wobble base pairs. The secondary structure prediction is performed by picking the best-scoring structure obtained after 50 folding simu- lation 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 *To whom correspondence should be addressed. Tel: +1 301 846 5536; Fax: +1 301 846 5598; Email: shapirbr@mail.nih.gov Published by Oxford University Press (2010). This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/ by-nc/2.5), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.