Nature inspired optimization algorithm for prediction of “minimum free energy” “RNA secondary structure” | Journal of Reliable Intelligent Environments Skip to main content
Springer Nature Link
Log in

Nature inspired optimization algorithm for prediction of “minimum free energy” “RNA secondary structure”

  • Original Article
  • Published:
Journal of Reliable Intelligent Environments Aims and scope Submit manuscript

Abstract

Over the last few years, many optimization algorithms have been developed to predict the optimal secondary structure of ribonucleic acid (RNA) with “minimum free energy” (MFE). These algorithms are either inspired by dynamic programming or by meta-heuristic techniques. RNA participates in several biological activities in the organism. These activities involve protein synthesis, understanding the functional behavior of RNA molecules, coding, decoding and gene expression, carrier of transferring genetic information, formation of protein, catalyst in biomedical reactions and structural molecule in cellular organelles, transcription, etc. Beside the said activities, the major role of RNA is in developing new drugs and understanding several diseases occurred due to genetic disorder and viruses. For the above said activities, it is required to predict the correct RNA secondary structure having minimum free energy with desired prediction accuracy. This paper presents a meta-heuristic optimization algorithm to obtain the optimal secondary structure of RNA with required functionality and requires less time than the others in the literature. The performance of the proposed algorithm is checked with different existing state-of-the-art techniques. It is found that the proposed algorithm gives better results against the other techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Kennedy J (2010) Particle swarm optimization. Encyclopedia of machine learning. Springer, New York, pp 760–766

    Google Scholar 

  2. Bäck T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Oxford

    MATH  Google Scholar 

  3. Coello CA, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems, vol 242. Kluwer Academic, New York

    MATH  Google Scholar 

  4. Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11(4):341–359

    MathSciNet  MATH  Google Scholar 

  5. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39(3):459–471

    MathSciNet  MATH  Google Scholar 

  6. Mishra KK, Tiwari S, Misra AK (2011) A bio inspired algorithm for solving optimization problems. In: 2nd International Conference on Computer and communication technology (ICCCT-2011), Allahabad, pp 653–659. https://doi.org/10.1109/ICCCT.2011.6075211

  7. Tripathi A, Garbyal P, Mishra KK, Misra AK (2014) Environmental adaption method for dynamic environment. In: Systems, man and cybernetics (SMC), 2014 IEEE international conference on 2014 Oct 5, IEEE, pp 216–221

  8. Tripathi A, Saxena N, Mishra KK, Misra AK (2015) An environmental adaption method with real parameter encoding for dynamic environment. J Intell Fuzzy Syst 29(5):2003–2015

    Google Scholar 

  9. Tripathi A, Saxena N, Mishra KK, Misra AK (2017) A nature inspired hybrid optimisation algorithm for dynamic environment with real parameter encoding. Int J Bio Inspired Comput 10(1):24–32

    Google Scholar 

  10. Mishra KK, Tripathi A, Tiwari S, Saxena N (2017) Evolution based memetic algorithm and its application in software cost estimation. J Intell Fuzzy Syst 32(3):2485–2498

    Google Scholar 

  11. Mishra KK, Tiwari S, Misra AK (2014) Improved environmental adaption method and its application in test case generation. J Intell Fuzzy Syst 27(5):2305–2317

    Google Scholar 

  12. Wang H, Wang W, Cui Z, Zhou X, Zhao J, Li Y (2018) A new dynamic firefly algorithm for demand estimation of water resources. Inf Sci 1(438):95–106

    MathSciNet  Google Scholar 

  13. He P, Deng Z, Wang H, Liu Z (2016) Model approach to grammatical evolution: theory and case study. Soft Comput 20(9):3537–3548

    MATH  Google Scholar 

  14. Lin W, Siyao X, Li J, Lingling X, Peng Z (2017) Design and theoretical analysis of virtual machine placement algorithm based on peak workload characteristics. Soft Comput 21(5):1301–1314

    MATH  Google Scholar 

  15. Lin W, Ziming W, Lin L, Wen A, Li J (2017) An ensemble random forest algorithm for insurance big data analysis. IEEE Access 5:16568–16575

    Google Scholar 

  16. Li Y, Wang G, Nie L, Wang Q (2018) Distance metric optimization driven convolutional neural network for age invariant face recognition. Pattern Recogn 75:51–62. https://doi.org/10.1016/j.patcog.2017.10.015

    Article  Google Scholar 

  17. Huang Y, Li W, Xue Y, Liang Z, Yu X, Wang X (2016) Efficient business process consolidation: combining topic features with structure matching. Soft Comput 22(2):645–657

    Google Scholar 

  18. Li Ya, Peng Z, Liang D, Chang H, Cai Z (2016) Facial age estimation by using stacked feature composition and selection. Vis Comput 32(12):1525–1536

    Google Scholar 

  19. Liu Y, Ling J, Liu Z, Shen J, Gao C (2017) Finger vein secure biometric template generation based on deep learning. Soft Comput 21(1):1–9

    Google Scholar 

  20. He P, Deng Z, Gao C, Wang X, Li J (2017) Model approach to grammatical evolution: deep-structured analyzing of model and representation. Soft Comput 21(18):5413–5423

    MATH  Google Scholar 

  21. Yuan C, Li X, Wu QMJ, Li J, Sun X (2017) Fingerprint liveness detection from different fingerprint materials using convolutional neural network and principal component analysis. CMC Comput Mater Contin 53(3):357–371

    Google Scholar 

  22. Doudna JA (2000) Structural genomics of RNA. Nat Struct Mol Biol 1(7):954–956

    Google Scholar 

  23. Higgs PG (2000) “RNA secondary structure”: physical and computational aspects. Q Rev Biophys 33(3):199–253

    Google Scholar 

  24. Doudna JA, Cech TR (2002) The chemical repertoire of natural ribozymes. Nature 418(6894):222–228

    Google Scholar 

  25. Coulson A (1987) Evolution of catalytic function. Cold Spring Harbor symposia on quantitative biology LII. Cold Spring Harbour Laboratory, New York. Genet Res 1989;53(02):147–148 (ISBN 0 87969 054 2)

  26. Tsang HH, Wiese KC (2007) SARNA-predict: a study of “RNA secondary structure” prediction using different annealing schedules. In: Computational intelligence and bioinformatics and computational biology, 2007. CIBCB’07. IEEE symposium on 2007 Apr 1. IEEE, pp 239–246

  27. Neethling M, Engelbrecht AP (2006) Determining “RNA secondary structure” using set-based particle swarm optimization. In: IEEE congress on evolutionary computation, 2006 Jul 16, pp 1670–1677

  28. Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Computer Science Department, University of Dortmund, Oxford University Press, Oxford (ISBN 978-0195099713)

    MATH  Google Scholar 

  29. Shapiro BA, Navetta J (1994) A massively parallel genetic algorithm for “RNA secondary structure” prediction. J Supercomput 8(3):195–207

    MATH  Google Scholar 

  30. Gultyaev AP, Van Batenburg FH, Pleij CW (1998) Dynamic competition between alternative structures in viroid RNAs simulated by an RNA folding algorithm. J Mol Biol 276(1):43–55

    Google Scholar 

  31. Woese CR, Pace NR (1993) Probing RNA Structure, Function, and History by Comparative Analysis. In: Gesteland RF, Atkins JF (eds) The RNA world, Second Edition© 1999 Cold Spring Harbor Laboratory Press 0-87969-561-7/99. pp 91–117

  32. Zuker M, Sankoff D (1984) “RNA secondary structure”s and their prediction. Bull Math Biol 46(4):591–621

    MATH  Google Scholar 

  33. Zuker M (2003) Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res 31(13):3406–3415

    Google Scholar 

  34. Isambert H, Siggia ED (2000) Modeling RNA folding paths with pseudoknots: application to hepatitis delta virus ribozyme. Proc Natl Acad Sci 97(12):6515–6520

    Google Scholar 

  35. Reeder J, Giegerich R (2004) Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinform 5:104. https://doi.org/10.1186/1471-2105-5-104

    Google Scholar 

  36. Wiese KC, Glen E (2003) A permutation-based genetic algorithm for the RNA folding problem: a critical look at selection strategies, crossover operators, and representation issues. Biosystems 72(1):29–41

    Google Scholar 

  37. Clote P (2005) An efficient algorithm to compute the landscape of locally optimal “RNA secondary structure”s with respect to the Nussinov–Jacobson energy model. J Comput Biol 12(1):83–101

    MathSciNet  Google Scholar 

  38. Serra MJ, Turner DH (1995) Predicting thermodynamic properties of RNA. Methods Enzymol 259:242

    Google Scholar 

  39. Xia T, SantaLucia J Jr, Burkard ME, Kierzek R, Schroeder SJ, Jiao X, Cox C, Turner DH (1998) Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson–Crick base pairs. Biochemistry 37(42):14719–14735

    Google Scholar 

  40. Wiese KC, Goodwin SD (2001) Keep-best reproduction: a local family competition selection strategy and the environment it flourishes in. Constraints. 6(4):399–422

    MATH  Google Scholar 

  41. Whitley D, Starkweather T, Shaner D (1991) The traveling salesman and sequence scheduling: quality solutions using genetic edge recombination. Colorado State University, Department of Computer Science, Fort Collins

    Google Scholar 

  42. Oliver IM, Smith DJ, Holland JRC (1987) A study of permutation crossover operators on the travelling salesman problem. Genetic algorithms and their applications. Lawrence Erlbaum Associates, Hilladale

    Google Scholar 

  43. Geem ZW (2005) Harmony search in water pump switching problem. In: Wang L, Chen K, Ong YS (eds) Advances in Natural Computation. ICNC 2005. Lecture Notes in Computer Science, vol 3612. Springer, Berlin, Heidelberg

    Google Scholar 

  44. Geem ZW, Kim JH, Loganathan GV (2001) A new heuristic optimization algorithm: harmony search. Simulation 76(2):60–68

    Google Scholar 

  45. Mohsen AM, Khader AT, Ramachandram D (2010) An optimization algorithm based on harmony search for RNA secondary structure prediction. In: Geem ZW (eds) Recent Advances In Harmony Search Algorithm. Studies in Computational Intelligence, vol 270. Springer, Berlin, Heidelberg

    Google Scholar 

  46. Geem ZW (eds) (2010) Recent advances in harmony search algorithm. Studies in Computational Intelligence, vol 270. Springer, Berlin, Heidelberg

    MATH  Google Scholar 

  47. Lee KS, Geem ZW (2005) A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Comput Methods Appl Mech Eng 194(36):3902–3933

    MATH  Google Scholar 

  48. Mahdavi M, Fesanghary M, Damangir E (2007) An improved harmony search algorithm for solving optimization problems. Appl Math Comput 188(2):1567–1579

    MathSciNet  MATH  Google Scholar 

  49. Neethling M, Matthee CA, Bowie RC, Von der Heyden S (2008) Evidence for panmixia despite barriers to gene flow in the southern African endemic, Caffrogobius caffer (Teleostei: Gobiidae). BMC Evol Biol 8(1):1

    Google Scholar 

  50. Geis M, Middendorf M (2011) Particle swarm optimization for finding “RNA secondary structure”s. Int J Intell Comput Cybern 4(2):160–186

    MathSciNet  Google Scholar 

  51. Liu YN, Dong H, Zhang H, Wang G, Li Z, Chen HL (2011) Prediction of “RNA secondary structure” based on particle swarm optimization. Chem Res Chin Univ 27(1):108–112

    Google Scholar 

  52. Tsang HH, Wiese KC (2010) SARNA-predict: accuracy improvement of “RNA secondary structure” prediction using permutation-based simulated annealing. IEEE ACM Trans Comput Biol Bioinform 7(4):727–740

    Google Scholar 

  53. Yu J, Zhang C, Liu Y, Li X (2010) Simulating the folding pathway of “RNA secondary structure” using the modified ant colony algorithm. J Bionic Eng 7(4):382–389

    Google Scholar 

  54. Wu H, Shi YF, Jin X, Wang G, Dong H (2011) A fuzzy adaptive particle swarm optimization for “RNA secondary structure” prediction. In: Information science and technology (ICIST), 2011 international conference on 2011 Mar 26, IEEE, pp 1390–1393

  55. Xing C, Wang G, Wang Y, Shen W, Liang Y, Ji Z (2011) A novel method for “RNA secondary structure” prediction. In: Natural computation (ICNC), 2011 seventh international conference on 2011 Jul 26, vol 2, IEEE, pp 1136–1140

  56. Wund MA (2012) Assessing the impacts of phenotypic plasticity on evolution. Integr Comp Biol 52(1):5–15

    Google Scholar 

  57. Mathews DH (2006) Predicting “RNA secondary structure” by free energy minimization. Theor Chem Acc 116(1–3):160–168

    Google Scholar 

  58. Zuker M (1994) Prediction of RNS secondary structure by energy minimization, Volume 25 of Computer analysis of sequence data: part II, Griffin AM, Griffin HG (eds), Chapter 23, CRC Press, Inc., Totowa, NJ, pp 267–294

  59. Wuchty S, Fontana W, Hofacker IL, Schuster P (1999) Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers 49(2):145–165

    Google Scholar 

  60. Geis M, Middendorf M (2007) A particle swarm optimizer for finding “minimum free energy” “RNA secondary structure”s. In: Swarm intelligence symposium, 2007. SIS 2007. IEEE 2007 Apr 1, IEEE, pp 1–8

  61. Tsang HH, Wiese KC (2006) SARNA-Predict: a simulated annealing algorithm for “RNA secondary structure” prediction. In: Computational intelligence and bioinformatics and computational biology, CIBCB’06, 2006 IEEE symposium on 2006 Sep 28, IEEE, pp 1–10

  62. Hendriks A (2005) A parallel evolutionary algorithm for RNA secondary structure prediction. Master’s thesis, Simon Fraser University. http://summit.sfu.ca/item/10224

  63. Mohsen A, Khader A, Ramachandram D, Ghallab A (2010) Predicting the “minimum free energy” “RNA secondary structure”s using harmony search algorithm. Int J Biol Life Sci 6(3):157–163

    Google Scholar 

  64. Zuker M, Stiegler P (1981) Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res 9(1):133–148

    Google Scholar 

  65. Zuker M (2003) Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res 31:3406–3415

    Google Scholar 

  66. http://www.ncbi.nlm.nih.gov/refseq/. Accessed 30 Apr 2016

  67. http://www.arb-silva.de/. Accessed 30 Apr 2016

  68. http://www.science.co.il/Biomedical/RNA-Databases.asp. Accessed 30 Apr 2016. http://www.rnasoft.ca/strand/. Accessed 30 Apr 2016

  69. Cannone JJ, Subramanian S, Schnare MN et al (2002) The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs. BMC Bioinform 3:15. https://doi.org/10.1186/1471-2105-3-15

    Google Scholar 

  70. Ray SS, Pal SK (2012) RNA secondary structure prediction using soft computing. IEEE ACM Trans Comput Biol Bioinf 10(1):2–17

    Google Scholar 

  71. Doshi KJ, Cannone JJ, Cobaugh CW, Gutell RR (2004) Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for RNA secondary structure prediction. BMC Bioinform 5(1):105

    Google Scholar 

  72. Coronato A, Paragliola G (2017) A structured approach for the designing of safe AAL applications. Expert Syst Appl 85:1–13

    Google Scholar 

  73. Thomas BL, Crandall AS, Cook DJ (2016) A genetic algorithm approach to motion sensor placement in smart environments. J Reliab Intell Environ 2(1):3–16

    Google Scholar 

  74. Coronato A, De Florio V, Bakhouya M, Serugendo GDM (2012) Formal modeling of socio-technical collective adaptive systems. In: 2012 IEEE sixth international conference on self-adaptive and self-organizing systems workshops, IEEE, pp 187–192

  75. Bakhouya M, Campbell R, Coronato A, Pietro GD, Ranganathan A (2012) Introduction to special section on formal methods in pervasive computing. ACM Trans Auton Adapt Syst (TAAS) 7(1):6

    Google Scholar 

  76. Preuveneers D, Joosen W (2016) Semantic analysis and verification of context-driven adaptive applications in intelligent environments. J Reliab Intell Environ 2(2):53–73

    Google Scholar 

  77. Coronato A (2018) Engineering high quality medical software: regulations, standards, methodologies and tools for certification (Healthcare Technologies, 2018) IET Digital Library. https://digitallibrary.theiet.org/content/books/he/pbhe012e

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of IT, G. L. Bajaj Institute of Technology & Management, Greater Noida, India

    Ashish Tripathi & P. C. Vashist

  2. CSED, MNNIT, Allahabad, India

    K. K. Mishra

  3. CSED, ABES Engineering College, Ghaziabad, India

    Shailesh Tiwari

Authors
  1. Ashish Tripathi
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. K. K. Mishra
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Shailesh Tiwari
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. P. C. Vashist
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Shailesh Tiwari.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tripathi, A., Mishra, K.K., Tiwari, S. et al. Nature inspired optimization algorithm for prediction of “minimum free energy” “RNA secondary structure”. J Reliable Intell Environ 5, 241–257 (2019). https://doi.org/10.1007/s40860-019-00091-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40860-019-00091-0

Keywords