Predicting the Minimum Free Energy RNA Secondary Structures using Harmony Search Algorithm

Authors: Abdulqader M. Mohsen, Ahamad Tajudin Khader, Dhanesh Ramachandram, Abdullatif Ghallab

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.

Keywords: Metaheuristic algorithms, dynamic programming algorithms, harmony search optimization, RNA folding, Minimum free energy.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078655

References:

[1] J. A. Doudna and T. R. Cech, "The chemical repertoire of natural ribozymes," Nature, vol. 418, no. 6894, pp. 222-228, 2002.
[2] J. L. Hansen, T. M. Schmeing, P. B. Moore, and T. A. Steitz, "Structural insights into peptide bond formation," in Proceedings of the National Academy of Sciences, vol. 99, 2002, pp. 11 670-11 675.
[3] J. Bachellerie, J. Cavaill, and A. Httenhofer, "The expanding snorna world," Biochimie, vol. 84, no. 8, pp. 775-790(16), August 2002.
[4] G. Meister and T. Tuschl, "Mechanisms of gene silencing by doublestranded rna," Nature, vol. 431, pp. 343-349, 2004.
[5] H. Tsang and K. Wiese, "Sarna-predict: A study of rna secondary structure prediction using different annealing schedules," in Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, 2007, pp. 239-246.
[6] M. Neethling and A. Engelbrecht, "Determining rna secondary structure using set-based particle swarm optimization," in IEEE Congress on Evolutionary Computation(CEC2006), 2006, pp. 1670-1677.
[7] K. J. Doshi, J. J. Cannone, C. W. Cobaugh, and R. R. Gutell, "Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for rna secondary structure prediction," BMC Bioinformatics, vol. 5, no. 105, pp. 1471-2105, 2004.
[8] D. H. Mathews, "Revolutions in rna secondary structure prediction," Journal of Molecular Biology, vol. 359, p. 526532, 2006.
[9] R. Nussinov, G. Pieczenik, J. R. Griggs, and D. J. Kleitman, "Algorithms for loop matchings," SIAM Journal on Applied Mathematics, vol. 35, no. 1, pp. 68-82, 1978.
[10] R. Nussinov and A. Jacobson, "Fast algorithm for predicting the secondary structure of single-stranded rna," Proc Natl Acad Sci U S A, vol. 77, no. 11, pp. 6309-6313, 1980.
[11] M. Zuker and P. Stiegler, "Optimal computer folding of large rna sequences using thermodynamics and auxiliary information," Nucl. Acids. Res, vol. 9, no. 1, pp. 133-148, 1981.
[12] M. Zuker, "Prediction of rna secondary structure by energy minimization," in Computer Analysis of Sequence Data, ser. Methods in Molecular Biology, M. G. Annette and G. G. Hugh, Eds. Humana Press, 1994, pp. 267-294, 10.1385/0-89603-276-0:267.
[13] ÔÇöÔÇö, "Mfold web server for nucleic acid folding and hybridization prediction," Nucleic Acids Research, vol. 31, no. 13, p. 34063415, 2003.
[14] I. Hofacker, W. Fontana, P. Stadler, S. Bonhoeffer, M. Tacker, and P. Schuster, "Fast folding and comparison of rna secondary structures (the vienna rna package)," Monatshefte f. Chemie, vol. 125, pp. 167-188, 1994.
[15] A. Gultyaev, F. van Batenburg, and C. Pleij, "Dynamic competition between alternative structures in viroid rnas simulated by an rna folding algorithm," Journal of Molecular Biology, vol. 276, no. 1, pp. 43-55, 1998.
[16] K. Wiese, A. Deschnes, and A. Hendriks, "Rnapredict - an evolutionary algorithm for rna secondary structure prediction," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 5, no. 1, pp. 25-41, 2007.
[17] K. C.Wiese and A. Hendriks, "Comparison of p-rnapredict and mfold algorithms for rna secondary structure prediction," Bioinformatics, vol. 22, no. 8, p. 934942, 2006.
[18] H. Tsang and K. Wiese, "The signifcance of thermodynamic models in the accuracy improvement of rna secondary structure prediction using permutation-based simulated annealing," in Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, 2007, pp. 3879- 3885.
[19] M. Geis and M. Middendorf, "A particle swarm optimizer for finding minimum free energy rna secondary structures," in Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, 2007, pp. 1-8.
[20] H. H. Tsang, "Sarna-predict: A permutation-based simulated annealing algorithm for rna secondary structure prediction," Ph.D. dissertation, Simon Fraser University, 2007.
[21] Z. W. Geem, J. H. Kim, and G. Loganathan, "A new heuristic optimization algorithm: Harmony search," SIMULATION, vol. 76, no. 2, pp. 60-68, 2001.
[22] M. Mahdavi, M. Fesanghary, and E. Damangir, "An improved harmony search algorithm for solving optimization problems," Applied Mathematics and Computation, vol. 188, no. 2, pp. 1567-1579, 2007.
[23] D. H. Mathews, "Predicting rna secondary structure by free energy minimization," Theoretical Chemistry Accounts:Theory, Computation, and Modeling, vol. 116(1-3), pp. 160-168, 2006.
[24] K. C. Wiese, E. Glen, and A. Vasudevan, "jviz.rna - a java tool for rna secondary structure visualization," IEEE Transactions on NanoBioscience, vol. 4, no. 3, pp. 212-218, 2005.
[25] D. M. Layton and R. Bundschuh, "A statistical analysis of rna folding algorithms through thermodynamic parameter perturbation," Nucleic Acids Research, vol. 33, no. 2, p. 519524, 2005.
[26] A. Hendriks, "A parallel evolutionary algorithm for rna secondary structure prediction," Ph.D. dissertation, Simon Fraser University, May2005.
[27] B. Alatas, "Chaotic harmony search algorithms," Applied Mathematics and Computation, vol. 216, no. 9, pp. 2687 - 2699, 2010.
[Online]. Available: http://www.sciencedirect.com/science/article/B6TY8- 4YPPPWP-6/2/489c124258d50da8d1930a2be60e777a
[28] K. S. Lee and Z. W. Geem, "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice," Computer Methods in Applied Mechanics and Engineering, vol. 194, no. 36-38, pp. 3902-3933, 2005.
[29] Z. W. Geem, "Harmony search in water pump switching problem," ICNC, vol. 3, pp. Pp 751-760, 2005.
[30] J. J. Cannone, S. Subramanian, M. N. Schnare, J. R. Collett, L. D-Souza, L. N. Du Y, Feng B, M. L.V, M. K.M, P. N, Y. N. Shang Z, and G. R.R., "The comparative rna web (crw) site: an online database of comparative sequence and structure information for ribosomal,intron, and other rnas," BMC Bioinformatics, vol. 3, no. 35, pp. 169-172, 2002.