Skip to main content

Advertisement

SpringerLink
Log in

Chemical reaction optimization for RNA structure prediction

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

RNA Structure Prediction (RSP) is an optimization problem, where a stable secondary structure is obtained from an RNA primary sequence. To solve the RSP problem, many exact and metaheuristic algorithms were established in recent years. We have proposed an approach based on metaheuristic algorithm named Chemical Reaction Optimization (CRO) to solve the RSP problem. CRO is a population-based metaheuristic which has been employed in different optimization problems and works better than all other related existing algorithms. We have redesigned the reaction operators of CRO algorithm and calculated the minimum free energy of the RNA structure to solve RSP problem. The operators spread out the population entirely on the solution space using both local and global searches and find the better structure, which makes the proposed algorithm more unique. We have designed a novel operator called Repair function to verify and remove the repeated stem from the solution of an RNA sequence, which makes the process more time efficient. Both the quality of solutions and execution time are considered in designing the basic operators and the repair function. Thus, the proposed methodology gives robustness, efficiency, and effectiveness in solving the problem. The results of the proposed CRO based algorithm for RSP problem are compared with genetic algorithm (RNAPredict), simulated annealing algorithm (SARNA-Predict), coincidence algorithm (COIN), two-level particle swarm optimization algorithm (TL-PSOfold) and Changing Range Bat Algorithm (CRBA) to present that, the proposed work gives better results than those. The significance testing using Kruskal-Wallis test followed by post-hoc analysis also proves that the proposed work outperforms the five related methods.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

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
Fig. 10

Similar content being viewed by others

References

  1. Ray SS, Pal SK (2013) RNA Secondary structure prediction using soft computing. IEEE/ACM Trans Comput Biol Bioinform 10:2–17

    Article  Google Scholar 

  2. Grypma P, Tsang HH (2014) SARNA-Predict: using adaptive annealing schedule and inversion mutation operator for RNA secondary structure prediction. In: 2014 IEEE symposium on computational intelligence in multi-criteria decision-making (MCDM). IEEE, pp 150–156

  3. McMellan N (2006) RNA secondary structure prediction using ant colony optimisation. Master Thesis, School of Informatics, University of Edinburgh

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

    Article  Google Scholar 

  5. Eddy SR (2004) How do RNA folding algorithms work? Nat Biotechnol 22:1457

    Article  Google Scholar 

  6. Schmitz M, Steger G (1996) Description of RNA folding by simulated annealing. J Mol Biol 255:254–266

    Article  Google Scholar 

  7. Wiese KC, Deschenes AA, Hendriks AG (2008) Rnapredict—an evolutionary algorithm for RNA secondary structure prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 5:25–41

    Article  Google Scholar 

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

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

  10. Liu Y, Dong H, Zhang H et al (2011) Prediction of RNA secondary structure based on particle swarm optimization. Chem Res Chin Univ 27:108–112

    Google Scholar 

  11. Xing C, Wang G, Wang Y et al (2011) A novel method for RNA secondary structure prediction. In: 2011 7th international conference on natural computation (ICNC). IEEE, pp 1136–1140

  12. Xing C, Wang G, Wang Y et al (2012) PSOFold: a metaheuristic for RNA folding. J Comput Inf Syst 8:915–923

    Google Scholar 

  13. Srikamdee S, Wattanapornprom W, Chongstitvatana P (2016) RNA secondary structure prediction with coincidence algorithm. In: 16th international symposium on communications and information technologies (ISCIT), 2016. IEEE, pp 686–690

  14. Truong TK, Li K, Xu Y (2013) Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem. Appl Soft Comput 13:1774–1780

    Article  Google Scholar 

  15. Lam AY, Li VO (2010) Chemical-reaction-inspired metaheuristic for optimization. IEEE Trans Evol Comput 14:381–399

    Article  Google Scholar 

  16. Lam AY, Li VO (2010) Chemical reaction optimization for cognitive radio spectrum allocation. In: Global telecommunications conference (GLOBECOM 2010), 2010 IEEE. IEEE, pp 1–5

  17. Pan B, Lam AY, Li VO (2011) Network coding optimization based on chemical reaction optimization. In: Global telecommunications conference (GLOBECOM 2011), 2011 IEEE. IEEE, pp 1–5

  18. Truong TK, Li K, Xu Y et al (2013) An artificial chemical reaction optimization algorithm for multiple-choice knapsack problem. In: Proceedings on the international conference on artificial intelligence (ICAI). The Steering Committee of the World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp), p 1

  19. Lalwani S, Kumar R, Gupta N (2016) An efficient two-level swarm intelligence approach for RNA secondary structure prediction with bi-objective minimum free energy scores. Swarm Evol Comput 27:68–79

    Article  Google Scholar 

  20. Mizuno H, Sundaralingam M (1978) Stacking of Crick Wobble pair and Watson-Crick pair: stability rules of GU pairs at ends of helical stems in tRNAs and the relation to codon-anticodon Wobble interaction. Nucleic Acids Res 5:4451–4462

    Article  Google Scholar 

  21. Xia T, SantaLucia J Jr, Burkard ME, et al. (1998) Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs. Biochemistry 37:14719–14735

    Article  Google Scholar 

  22. Turner DH, Mathews DH (2009) NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res 38:D280–D282

    Article  Google Scholar 

  23. Rivas E, Eddy SR (1999) A dynamic programming algorithm for RNA structure prediction including pseudoknots1. J Mol Biol 285:2053–2068

    Article  Google Scholar 

  24. Liu Z, Zhao S, Ye H et al (2016) The PTAS of Prediction for RNA Pseudoknotted Structure. In: 12th international conference on computational intelligence and security (CIS), 2016. IEEE, pp 1–4

  25. Akutsu T (2000) Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discret Appl Math 104:45–62

    Article  MathSciNet  MATH  Google Scholar 

  26. 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 Bioinformatics 3:2

    Article  Google Scholar 

  27. Tong K-K, Cheung K-Y, Lee K-H, Leung K-S (2013) GAknot: RNA secondary structures prediction with pseudoknots using Genetic Algorithm. In: 2013 IEEE symposium on computational intelligence in bioinformatics and computational biology (CIBCB). IEEE, pp 136–142

  28. Lam AY, Li VO (2012) Chemical reaction optimization: a tutorial. Memetic Computing 4:3–17

    Article  Google Scholar 

  29. Islam MR, Saifullah CK, Asha ZT, Ahamed R (2018) Chemical reaction optimization for solving longest common subsequence problem for multiple string. Soft Comput, pp 1–25

  30. Andronescu M, Bereg V, Hoos HH, Condon A (2008) RNA STRAND: the RNA secondary structure and statistical analysis database. BMC Bioinformatics 9:340

    Article  Google Scholar 

  31. Lorenz R, Bernhart SH, Zu Siederdissen CH et al (2011) ViennaRNA package 2.0. Algorithms Mol Biol 6:26

    Article  Google Scholar 

  32. Cui Z, Cao Y, Li F, Zhu Z (2015) Changing range bat algorithm for RNA secondary structure prediction. J Comput Theor Nanosci 12:1968–1971

    Article  Google Scholar 

  33. Miao Z, Westhof E (2017) RNA Structure: advances and assessment of 3D structure prediction. Annu Rev Biophys 46:483–503

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science, Engineering Discipline, Khulna University, Khulna, 9208, Bangladesh

    Rayhanul Kabir & Rafiqul Islam

Authors
  1. Rayhanul Kabir
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rafiqul Islam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rayhanul Kabir.

Ethics declarations

Conflict of interests

The authors have no conflict of interest.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kabir, R., Islam, R. Chemical reaction optimization for RNA structure prediction. Appl Intell 49, 352–375 (2019). https://doi.org/10.1007/s10489-018-1281-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-018-1281-4

Keywords

Search

Navigation