Accelerating calculations of RNA secondary structure partition functions using GPUs

Algorithms for Molecular Biology

Harry A Stern¹  David H Mathews² 

[1] Center for Integrated Research Computing, Taylor Hall, University of Rochester, Rochester, NY, 14627, USA

[2] Department of Biochemistry & Biophysics and Center for RNA Biology, University of Rochester Medical Center, 601, Elmwood Avenue Box 712, Rochester, NY, 14642, USA

关键词: CUDA;    Graphical processing unit;    Partition function;    Secondary structure;    RNA;   

Others  :  793111
DOI  :  10.1186/1748-7188-8-29

 received in 2013-01-31, accepted in 2013-10-14,  发布年份 2013

【 摘 要 】

Background

RNA performs many diverse functions in the cell in addition to its role as a messenger of genetic information. These functions depend on its ability to fold to a unique three-dimensional structure determined by the sequence. The conformation of RNA is in part determined by its secondary structure, or the particular set of contacts between pairs of complementary bases. Prediction of the secondary structure of RNA from its sequence is therefore of great interest, but can be computationally expensive. In this work we accelerate computations of base-pair probababilities using parallel graphics processing units (GPUs).

Results

Calculation of the probabilities of base pairs in RNA secondary structures using nearest-neighbor standard free energy change parameters has been implemented using CUDA to run on hardware with multiprocessor GPUs. A modified set of recursions was introduced, which reduces memory usage by about 25%. GPUs are fastest in single precision, and for some hardware, restricted to single precision. This may introduce significant roundoff error. However, deviations in base-pair probabilities calculated using single precision were found to be negligible compared to those resulting from shifting the nearest-neighbor parameters by a random amount of magnitude similar to their experimental uncertainties. For large sequences running on our particular hardware, the GPU implementation reduces execution time by a factor of close to 60 compared with an optimized serial implementation, and by a factor of 116 compared with the original code.

Conclusions

Using GPUs can greatly accelerate computation of RNA secondary structure partition functions, allowing calculation of base-pair probabilities for large sequences in a reasonable amount of time, with a negligible compromise in accuracy due to working in single precision. The source code is integrated into the RNAstructure software package and available for download at http://rna.urmc.rochester.edu webcite.

【 授权许可】

   
2013 Stern and Mathews; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

【 参考文献 】

• [1]Doudna JA, Cech TR: The chemical repertoire of natural ribozymes. Nature 2002, 418:222.
• [2]Bachellerie JP, Cavaille J, Huttenhofer A: The expanding snoRNA world. Biochimie 2002, 84:775.
• [3]Walter P, Blobel G: Signal recognition particle contains a 7S RNA essential for protein translocation across the endoplasmic reticulum. Nature 1982, 299:691.
• [4]Dykxhoorn DM, Novina CD, Sharp PA: Killing the messenger: Short RNAs that silence gene expression. Nat Rev Mol Cell Biol 2003, 4:457.
• [5]Wu L, Belasco JG: Let me count the ways: Mechanisms of gene regulation by miRNAs and siRNAs. Mol Cell 2008, 29:1.
• [6]Bustamante C, Tinoco I Jr: How RNA folds. J Mol Biol 1999, 293:271.
• [7]Nawrocki EP, Kolbe DL, Eddy SR: Infernal 1.0: Inference of RNA alignments. Bioinformatics 2009, 25:1335.
• [8]Li X, Quon G, Lipshitz HD, Morris Q: Predicting in vivo binding sites of RNA-binding proteins using mRNA secondary structure. RNA 2010, 16:1096.
• [9]Lu ZJ, Mathews DH: Efficient siRNA selectrion using hybridization thermodynamics. Nucleic Acids Res 2007, 36:640.
• [10]Tafer H, Ameres SL, Obernosterer G, Gebeshuber CA, Schroeder R, Martinez J, Hofacker IL: The impact of target site accessibility on the deseign of effective siRNAs. Nat Biotechnol 2008, 26:578.
• [11]Turner DH, Mathews DH: NNDB: The nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res 2010, 38:D280.
• [12]Lorenz R, Bernhart SH, zu Siederdissen CH, Tafer H, Flamm C, Stadler PF, Hofacker IL: ViennaRNA package 2.0. Algorithms Mol Biol 2011, 6:26. BioMed Central Full Text
• [13]Sanders J, Kandrot E: CUDA by Example: An Introduction to General-Purpose GPU Programming. Boston: Addison-Wesley; 2011.
• [14]Farber RM: Topical perspective on massive threading and parallelism. J Mol Graph Model 2011, 30:82.
• [15]Gotz AW, Williamson MJ, Xu D, Poole D, Le Grand S, Walker RC: Routine microsecond molecular dynamics simulations with AMBER on GPUs. 1. Generalized Born. J Chem Theory Comput 2012, 8:1542.
• [16]Rizk G, Lavenier D: GPU accelerated RNA folding algorithm. Lect Notes Comput Sci 2009, 5544:1004.
• [17]Lei G, Dou Y, Wan W, Xia F, Li R, Ma M, Zou D: CPU-GPU hybrid accelerating the Zuker algorithm for RNA secondary structure prediction applications. BMC Genomics 2012, 13(Suppl 1):S14. BioMed Central Full Text
• [18]Mathews DH, Disney MD, Childs JL, Schroeder SJ, Zuker M, Turner DH: Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc Natl Acad Sci USA 2004, 101:7287.
• [19]Kim J, Walter AE, Turner DH: Thermodynamics of coaxially stacked helices with GA and CC mismatches. Biochemistry 1996, 35:13753.
• [20]Mathews DH: Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization. RNA 2004, 10:1178.
• [21]Lu ZJ, Gloor JW, Mathews DH: Improved RNA secondary structure prediction by maximizing expected pair accuracy. RNA 2009, 15:1805.
• [22]Bellaousov S, Mathews DH: ProbKnot: Fast prediction of RNA secondary structure including pseudoknots. RNA 2010, 16:1870.
• [23]Harmanci AO, Sharma G, Mathews DH: PARTS: Probabilistic alignment for RNA joint secondary structure predcition. Nucleic Acids Res 2008, 36:2406.
• [24]Harmanci AO, Sharma G, Mathews DH: Stochastic sampling of the RNA structural alignment space. Nucleic Acids Res 2009, 37:4063.
• [25]Harmanci AO, Sharma G, Mathews DH: Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign. BMC Bioinformatics 2011, 27:626.
• [26]Seetin MG, Mathews DH: TurboKnot: Rapid prediction of conserved RNA secondary structures including pseudoknots. Bioinformatics 2012, 28:792.
• [27]Reuter JS, Mathews DH: RNAstructure: software for RNA secondary structure prediction and analysis. BMC Bioinformatics 2010, 11:129. BioMed Central Full Text
• [28]Sprinzl M, Vassilenko KS: Compilation of tRNA sequences and sequences of tRNA genes. Nucleic Acids Res 2005, 33:D139.
• [29]Szymanski M, Barciszewska MZ, Barciszewski J, Erdmann VA: 5S ribosomal RNA database Y2K. Nucleic Acids Res 2000, 28:166.
• [30]Cannone JJ, Subramanian S, Schnare MN, Collett JR, D’Souza LM, Du Y, Feng B, Lin N, Madabusi LV, Muller KM, Pande N, Shang Z, Yu N, Gutell RR: The compariative RNA web (CRW) site: An online databae of comparative sequence and structure information for ribosomal, intron, and other RNAs. BMC Bioinformatics 2002, 3:2. BioMed Central Full Text
• [31]Cate JH, Gooding AR, Podell E, Zhou K, Golden BL, Kundrot CE, Cech TR, Doudna JA: Crystal structure of a group I ribozyme domain: Principles of RNA packing. Science 1996, 273:1678.
• [32]Larsen N, Samuelsson T, Zwieb C: The signal recognition particle database (SRPDB). Nucleic Acids Res 1998, 26:177.
• [33]Mathews DH, Banerjee A R Luan D D, Eickbush TH, Turner DH: Secondary structure model of the RNA recognized by the reverse transcriptase from the R2 retrotransposable element. RNA 1997, 3:1.
• [34]Michel F, Umesono K, Ozeki H: Comparative and functional anatomy of group II catalytic introns—a review. Gene 1989, 82:5.
• [35]Staunton DE, Marlin SD, Stratowa C, Dustin ML, Springer TA: Primary structure of ICAM-1 demonstrates interaction between members of the immunoglobulin and integrin supergene families. Cell 1988, 52:925.
• [36]Adachi A, Gendelman HE, Koenig S, Folks T, Willey R, Rabson A, Martin MA: Production of acquired immunodeficiency syndrome-associated retrovirus in human and nonhuman cells transfected with an infectious molecular clone. J Virol 1986, 59:284.
• [37]Xia T, Burkhard ME, Kierzek R, Schroeder SJ, Jaio X, Cox C, Turner DH, Santa Lucia J Jr: Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick pairs. Biochemistry 1998, 37:14719.
• [38]Zuker M: On finding all suboptimal foldings of an RNA molecule. Science 1989, 244:48.
• [39]Layton DM, Bundschuh R: A statistical analysis of RNA folding algorithms through thermodynamic parameter perturbation. Nucleic Acids Res 2005, 33:519.