Login Register Cart 0
Generic placeholder image

Current Bioinformatics

Editor-in-Chief

ISSN (Print): 1574-8936
ISSN (Online): 2212-392X

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

Prediction of RNA Secondary Structure Using Quantum-inspired Genetic Algorithms

Author(s): Sha Shi, Xin-Li Zhang, Le Yang, Wei Du, Xian-Li Zhao* and Yun-Jiang Wang*

Volume 15, Issue 2, 2020

Page: [135 - 143] Pages: 9

DOI: 10.2174/1574893614666190916154103

Price: $65

Abstract

Background: The prediction of RNA secondary structure using optimization algorithms is key to understand the real structure of an RNA. Evolutionary algorithms (EAs) are popular strategies for RNA secondary structure prediction. However, compared to most state-of-the-art software based on DPAs, the performances of EAs are a bit far from satisfactory.

Objective: Therefore, a more powerful strategy is required to improve the performances of EAs when applied to the prediciton of RNA secondary structures.

Methods: The idea of quantum computing is introduced here yielding a new strategy to find all possible legal paired-bases with the constraint of minimum free energy. The sate of a stem pool with size N is encoded as a population of QGA, which is represented by N quantum bits but not classical bits. The updating of populations is accomplished by so-called quantum crossover operations, quantum mutation operations and quantum rotation operations.

Results: The numerical results show that the performances of traditional EAs are significantly improved by using QGA with regard to not only prediction accuracy and sensitivity but also complexity. Moreover, for RNA sequences with middle-short length, QGA even improves the state-of-art software based on DPAs in terms of both prediction accuracy and sensitivity.

Conclusion: This work sheds an interesting light on the applications of quantum computing on RNA structure prediction.

Keywords: RNA secondary structure, prediction, quantum computing, genetic algorithm, quantum algorithms.

« Previous Next »
Graphical Abstract

[1]
Buratti E, Muro AF, Giombi M, Gherbassi D, Iaconcig A, Baralle FE. RNA folding affects the recruitment of SR proteins by mouse and human polypurinic enhancer elements in the fibronectin EDA exon. Mol Cell Biol 2004; 24(3): 1387-400.
[http://dx.doi.org/10.1128/MCB.24.3.1387-1400.2004] [PMID: 14729981]
[2]
Kozak M. Regulation of translation via mRNA structure in prokaryotes and eukaryotes. Gene 2005; 361: 13-37.
[http://dx.doi.org/10.1016/j.gene.2005.06.037]
[3]
Sharp PA. The Centrality of RNA. Cell 2009; 136(4): 577-80.
[http://dx.doi.org/10.1016/j.cell.2009.02.007]
[4]
Cruz J. The Dynamic Landscapes of RNA Architecture. Cell 2009; 136(4): 604-9.
[http://dx.doi.org/10.1016/j.cell.2009.02.003]
[5]
Ding Y, Tang Y, Kwok CK, Zhang Y, Bevilacqua PC, Assmann SM. In vivo genome-wide profiling of RNA secondary structure reveals novel regulatory features. Nature 2014; 505(7485): 696-700.
[http://dx.doi.org/10.1038/nature12756] [PMID: 24270811]
[6]
Tinoco I Jr, Bustamante C. How RNA folds. J Mol Biol 1999; 293(2): 271-81.
[http://dx.doi.org/10.1006/jmbi.1999.3001] [PMID: 10550208]
[7]
Proctor JR, Meyer IM. COFOLD: an RNA secondary structure prediction method that takes co-transcriptional folding into account. Nucleic Acids Res 2013; 41(9): e102
[http://dx.doi.org/10.1093/nar/gkt174] [PMID: 23511969]
[8]
Liu Y, Zhao Q, Zhang H, Xu R, Li Y, Wei L. A New Method to Predict RNA Secondary Structure Based on RNA Folding Simulation. IEEE/ACM Trans Comput Biol Bioinformatics 2016; 13(5): 990-5.
[http://dx.doi.org/10.1109/TCBB.2015.2496347] [PMID: 26552091]
[9]
Sun LZ, Zhang D, Chen SJ. Theory and Modeling of RNA Structure and Interactions with Metal Ions and Small Molecules. Annu Rev Biophys 2017; 46(1): 227-46.
[http://dx.doi.org/10.1146/annurev-biophys-070816-033920] [PMID: 28301768]
[10]
Zuber J, Sun H, Zhang X, McFadyen I, Mathews DH. A sensitivity analysis of RNA folding nearest neighbor parameters identifies a subset of free energy parameters with the greatest impact on RNA secondary structure prediction. Nucleic Acids Res 2017; 45(10): 6168-76.
[http://dx.doi.org/10.1093/nar/gkx170] [PMID: 28334976]
[11]
Batey RT, Gilbert SD, Montange RK. Structure of a natural guanine-responsive riboswitch complexed with the metabolite hypoxanthine. Nature 2004; 432(7015): 411-5.
[http://dx.doi.org/10.1038/nature03037] [PMID: 15549109]
[12]
Ferentz AE, Wagner G. NMR spectroscopy: a multifaceted approach to macromolecular structure. Q Rev Biophys 2000; 33(1): 29-65.
[http://dx.doi.org/10.1017/S0033583500003589] [PMID: 11075388]
[13]
Deschene A, Wiese KC, Poonian J. Comparison of dynamic programming and evolutionary algorithms for RNA secondary structure prediction 2004 Symposium on Computational Intelligence in Bioinformatics and Computational Biology.
[14]
Gutell RR, Lee JC, Cannone JJ. The accuracy of ribosomal RNA comparative structure models. Curr Opin Struct Biol 2002; 12(3): 301-10.
[http://dx.doi.org/10.1016/S0959-440X(02)00339-1] [PMID: 12127448]
[15]
Deng F, Ledda M, Vaziri S, Aviran S. Data-directed RNA secondary structure prediction using probabilistic modeling. RNA 2016; 22(8): 1109-19.
[http://dx.doi.org/10.1261/rna.055756.115] [PMID: 27251549]
[16]
Turner DH, Sugimoto N, Freier SM. RNA structure prediction. Annu Rev Biophys Biophys Chem 1988; 17(673): 167-92.
[http://dx.doi.org/10.1146/annurev.bb.17.060188.001123] [PMID: 2456074]
[17]
Mathews DH, Sabina J, Zuker M, Turner DH. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol 1999; 288(5): 911-40.
[http://dx.doi.org/10.1006/jmbi.1999.2700] [PMID: 10329189]
[18]
Higgs PG. RNA secondary structure: physical and computational aspects. Q Rev Biophys 2000; 33(3): 199-253.
[http://dx.doi.org/10.1017/S0033583500003620] [PMID: 11191843]
[19]
Zuker M. On finding all suboptimal foldings of an RNA molecule. Science 1989; 244(4900): 48-52.
[http://dx.doi.org/10.1126/science.2468181] [PMID: 2468181]
[20]
Shapiro BA, Navetta J. A massively parallel genetic algorithm for RNA secondary structure prediction. J Supercomput 1994; 8(3): 195-207.
[http://dx.doi.org/10.1007/BF01204728]
[21]
van Batenburg FH, Gultyaev AP, Pleij CWA. An APL-programmed genetic algorithm for the prediction of RNA secondary structure. J Theor Biol 1995; 174(3): 269-80.
[http://dx.doi.org/10.1006/jtbi.1995.0098] [PMID: 7545258]
[22]
Gultyaev AP, van Batenburg FH, Pleij CWA. The computer simulation of RNA folding pathways using a genetic algorithm. J Mol Biol 1995; 250(1): 37-51.
[http://dx.doi.org/10.1006/jmbi.1995.0356] [PMID: 7541471]
[23]
Shapiro BA, Wu JC. An annealing mutation operator in the genetic algorithms for RNA folding. Comput Appl Biosci 1996; 12(3): 171-80.
[http://dx.doi.org/10.1093/bioinformatics/12.3.171] [PMID: 8872384]
[24]
Fogel GB, Porto VW, Weekes DG, et al. Discovery of RNA structural elements using evolutionary computation. Nucleic Acids Res 2002; 30(23): 5310-7.
[http://dx.doi.org/10.1093/nar/gkf653] [PMID: 12466557]
[25]
Deschenes A, Wiese KC. Using Stacking-Energies (INN and INNHB) for Improving the Accuracy of RNA Secondary Structure Prediction with an Evolutionary AlgorithmA Comparison to Known Structures Proc 2004 IEEE Congress Evolutionary Computation 598-606.
[26]
Tong KK, Cheung KY, Lee KH, Leung KS.
[27]
Tsang HH, Wiese KC. SARNA-Predict: accuracy improvement of RNA secondary structure prediction using permutation-based simulated annealing. IEEE/ACM Trans Comput Biol Bioinformatics 2010; 7(4): 727-40.
[http://dx.doi.org/10.1109/TCBB.2008.97] [PMID: 21030739]
[28]
Han KH, Kim JH. Genetic quantum algorithm and its application to a combinatorial optimization problem. Proc Congr Evol Comput 1354-60.
[29]
Han KH, Kim JH. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans Evol Comput 2002; 6(6): 580-93.
[http://dx.doi.org/10.1109/TEVC.2002.804320]
[30]
Zuker M, Mathews DH, Turner DH. Algorithms and Thermo-dynamics for RNA Secondary Structure Prediction: A Practical Guide. RNA Biochemistry and Biotechnology 1999; 11-43.
[31]
Chuang I, Nielsen M. Quantum Computation and Quantum Information 2000.
[32]
Rafael LB. Quantum Genetic Algorithms for Computer Scientists. Computer 2016; 5: 24.
[http://dx.doi.org/10.3390/computers5040024]

Rights & Permissions Print Cite
Article Metrics
19
3
© 2024 Bentham Science Publishers | Privacy Policy