{"title":"Predicting the Minimum Free Energy RNA Secondary Structures using Harmony Search Algorithm","authors":"Abdulqader M. Mohsen, Ahamad Tajudin Khader,Dhanesh Ramachandram, Abdullatif Ghallab","volume":32,"journal":"International Journal of Computer and Information Engineering","pagesStart":2140,"pagesEnd":2147,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/12151","abstract":"
The physical methods for RNA secondary structure prediction are time consuming and expensive, thus methods for computational prediction will be a proper alternative. Various algorithms have been used for RNA structure prediction including dynamic programming and metaheuristic algorithms. Musician's behaviorinspired harmony search is a recently developed metaheuristic algorithm which has been successful in a wide variety of complex optimization problems. This paper proposes a harmony search algorithm (HSRNAFold) to find RNA secondary structure with minimum free energy and similar to the native structure. HSRNAFold is compared with dynamic programming benchmark mfold and metaheuristic algorithms (RnaPredict, SetPSO and HelixPSO). The results showed that HSRNAFold is comparable to mfold and better than metaheuristics in finding the minimum free energies and the number of correct base pairs.<\/p>\r\n","references":"[1] J. A. Doudna and T. R. Cech, \"The chemical repertoire of natural\r\nribozymes,\" Nature, vol. 418, no. 6894, pp. 222-228, 2002.\r\n[2] J. L. Hansen, T. M. Schmeing, P. B. Moore, and T. A. Steitz, \"Structural\r\ninsights into peptide bond formation,\" in Proceedings of the National\r\nAcademy of Sciences, vol. 99, 2002, pp. 11 670-11 675.\r\n[3] J. Bachellerie, J. Cavaill, and A. Httenhofer, \"The expanding snorna\r\nworld,\" Biochimie, vol. 84, no. 8, pp. 775-790(16), August 2002.\r\n[4] G. Meister and T. Tuschl, \"Mechanisms of gene silencing by doublestranded\r\nrna,\" Nature, vol. 431, pp. 343-349, 2004.\r\n[5] H. Tsang and K. Wiese, \"Sarna-predict: A study of rna secondary\r\nstructure prediction using different annealing schedules,\" in Proceedings\r\nof the IEEE Symposium on Computational Intelligence in Bioinformatics\r\nand Computational Biology, 2007, pp. 239-246.\r\n[6] M. Neethling and A. Engelbrecht, \"Determining rna secondary structure\r\nusing set-based particle swarm optimization,\" in IEEE Congress on\r\nEvolutionary Computation(CEC2006), 2006, pp. 1670-1677.\r\n[7] K. J. Doshi, J. J. Cannone, C. W. Cobaugh, and R. R. Gutell, \"Evaluation\r\nof the suitability of free-energy minimization using nearest-neighbor\r\nenergy parameters for rna secondary structure prediction,\" BMC Bioinformatics,\r\nvol. 5, no. 105, pp. 1471-2105, 2004.\r\n[8] D. H. Mathews, \"Revolutions in rna secondary structure prediction,\"\r\nJournal of Molecular Biology, vol. 359, p. 526532, 2006.\r\n[9] R. Nussinov, G. Pieczenik, J. R. Griggs, and D. J. Kleitman, \"Algorithms\r\nfor loop matchings,\" SIAM Journal on Applied Mathematics, vol. 35,\r\nno. 1, pp. 68-82, 1978.\r\n[10] R. Nussinov and A. Jacobson, \"Fast algorithm for predicting the\r\nsecondary structure of single-stranded rna,\" Proc Natl Acad Sci U S\r\nA, vol. 77, no. 11, pp. 6309-6313, 1980.\r\n[11] M. Zuker and P. Stiegler, \"Optimal computer folding of large rna sequences\r\nusing thermodynamics and auxiliary information,\" Nucl. Acids.\r\nRes, vol. 9, no. 1, pp. 133-148, 1981.\r\n[12] M. Zuker, \"Prediction of rna secondary structure by energy minimization,\"\r\nin Computer Analysis of Sequence Data, ser. Methods in Molecular\r\nBiology, M. G. Annette and G. G. Hugh, Eds. Humana Press, 1994,\r\npp. 267-294, 10.1385\/0-89603-276-0:267.\r\n[13] \u00d4\u00c7\u00f6\u00d4\u00c7\u00f6, \"Mfold web server for nucleic acid folding and hybridization\r\nprediction,\" Nucleic Acids Research, vol. 31, no. 13, p. 34063415, 2003.\r\n[14] I. Hofacker, W. Fontana, P. Stadler, S. Bonhoeffer, M. Tacker, and\r\nP. Schuster, \"Fast folding and comparison of rna secondary structures\r\n(the vienna rna package),\" Monatshefte f. Chemie, vol. 125, pp. 167-188,\r\n1994.\r\n[15] A. Gultyaev, F. van Batenburg, and C. Pleij, \"Dynamic competition\r\nbetween alternative structures in viroid rnas simulated by an rna folding\r\nalgorithm,\" Journal of Molecular Biology, vol. 276, no. 1, pp. 43-55,\r\n1998.\r\n[16] K. Wiese, A. Deschnes, and A. Hendriks, \"Rnapredict - an evolutionary\r\nalgorithm for rna secondary structure prediction,\" IEEE\/ACM Transactions\r\non Computational Biology and Bioinformatics, vol. 5, no. 1, pp.\r\n25-41, 2007.\r\n[17] K. C.Wiese and A. Hendriks, \"Comparison of p-rnapredict and mfold algorithms\r\nfor rna secondary structure prediction,\" Bioinformatics, vol. 22,\r\nno. 8, p. 934942, 2006.\r\n[18] H. Tsang and K. Wiese, \"The signifcance of thermodynamic models in\r\nthe accuracy improvement of rna secondary structure prediction using\r\npermutation-based simulated annealing,\" in Proceedings of the IEEE\r\nCongress on Evolutionary Computation, Singapore, 2007, pp. 3879-\r\n3885.\r\n[19] M. Geis and M. Middendorf, \"A particle swarm optimizer for finding\r\nminimum free energy rna secondary structures,\" in Swarm Intelligence\r\nSymposium, 2007. SIS 2007. IEEE, 2007, pp. 1-8.\r\n[20] H. H. Tsang, \"Sarna-predict: A permutation-based simulated annealing\r\nalgorithm for rna secondary structure prediction,\" Ph.D. dissertation,\r\nSimon Fraser University, 2007.\r\n[21] Z. W. Geem, J. H. Kim, and G. Loganathan, \"A new heuristic optimization\r\nalgorithm: Harmony search,\" SIMULATION, vol. 76, no. 2,\r\npp. 60-68, 2001.\r\n[22] M. Mahdavi, M. Fesanghary, and E. Damangir, \"An improved harmony\r\nsearch algorithm for solving optimization problems,\" Applied Mathematics\r\nand Computation, vol. 188, no. 2, pp. 1567-1579, 2007.\r\n[23] D. H. Mathews, \"Predicting rna secondary structure by free energy\r\nminimization,\" Theoretical Chemistry Accounts:Theory, Computation,\r\nand Modeling, vol. 116(1-3), pp. 160-168, 2006.\r\n[24] K. C. Wiese, E. Glen, and A. Vasudevan, \"jviz.rna - a java tool for\r\nrna secondary structure visualization,\" IEEE Transactions on NanoBioscience,\r\nvol. 4, no. 3, pp. 212-218, 2005.\r\n[25] D. M. Layton and R. Bundschuh, \"A statistical analysis of rna folding\r\nalgorithms through thermodynamic parameter perturbation,\" Nucleic\r\nAcids Research, vol. 33, no. 2, p. 519524, 2005.\r\n[26] A. Hendriks, \"A parallel evolutionary algorithm for rna secondary structure\r\nprediction,\" Ph.D. dissertation, Simon Fraser University, May2005.\r\n[27] B. Alatas, \"Chaotic harmony search algorithms,\" Applied Mathematics\r\nand Computation, vol. 216, no. 9, pp. 2687 - 2699, 2010. [Online].\r\nAvailable: http:\/\/www.sciencedirect.com\/science\/article\/B6TY8-\r\n4YPPPWP-6\/2\/489c124258d50da8d1930a2be60e777a\r\n[28] K. S. Lee and Z. W. Geem, \"A new meta-heuristic algorithm for continuous\r\nengineering optimization: harmony search theory and practice,\"\r\nComputer Methods in Applied Mechanics and Engineering, vol. 194,\r\nno. 36-38, pp. 3902-3933, 2005.\r\n[29] Z. W. Geem, \"Harmony search in water pump switching problem,\"\r\nICNC, vol. 3, pp. Pp 751-760, 2005.\r\n[30] J. J. Cannone, S. Subramanian, M. N. Schnare, J. R. Collett, L. D-Souza,\r\nL. N. Du Y, Feng B, M. L.V, M. K.M, P. N, Y. N. Shang Z, and G. R.R.,\r\n\"The comparative rna web (crw) site: an online database of comparative\r\nsequence and structure information for ribosomal,intron, and other rnas,\"\r\nBMC Bioinformatics, vol. 3, no. 35, pp. 169-172, 2002.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 32, 2009"}