Predicting the Minimum Free Energy RNA Secondary Structures using Harmony Search Algorithm
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:61182", author = "Abdulqader M. Mohsen and Ahamad Tajudin Khader and Dhanesh Ramachandram and Abdullatif Ghallab", title = "Predicting the Minimum Free Energy RNA Secondary Structures using Harmony Search Algorithm", 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.", volume = "3", number = "8", pages = "2101-7", }
