利用量子遗传算法实现RNA二级结构预测

doi:10.3969/j.issn.1001-2400.2018.04.020

Abstract

Abstract:

Due to the high complexity and low search efficiency of the traditional algorithm based on the minimum free energy model, a quantum genetic algorithm for RNA secondary structure prediction is proposed, where the group is initialized by coding with qubits and the corresponding evolutions are accomplished by quantum unitary operations (i.e., quantum gates). By using this strategy, the scale of the required groups is reduced significantly due to the parallelism of quantum computing which also leads to a more powerful searching ability compared with the classical genetic algorithm. Based on the sequences offered by RNA STRAND database, the algorithm was tested by quantum simulations. Numerical results show that, for even only 20% of groups exploited with respect to the classical genetic algorithm, the prediction accuracy yielded by this strategy is still superior to that of the classical one, and that the number of evolution rounds is also obviously reduced by using this algorithm.

Key words: quantum computing, quantum algorithms, quantum simulation, ribonucleic acid, secondary structureprediction

LIU Yang;LI Jiaqiao;WANG Fan;WANG Zengbin;SHI Sha. RNA secondary structure prediction using the quantum genetic algorithm[J].Journal of Xidian University, 2018, 45(4): 112-117.

References

［1］ MORRIS K V, MATTICK J S. The Rise of Regulatory RNA［J］. Nature Reviews Genetics, 2014, 15(6): 423-437.
［2］ DING Y, TANG Y, KWOK C K, et al. In Vivo Genome-wide Profiling of RNA Secondary Structure Reveals Novel Regulatory Features［J］. Nature, 2014, 505(7485): 696-700.
［3］ LIU Y N, ZHAO Q, ZHANG H, et al. A New Method to Predict RNA Secondary Structure Based on RNA Folding Simulation ［J］. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2016, 13(5): 990-995.
［4］ DENG F, LEDDA M, VAZIRI S, et al. Data-directed RNA Secondary Structure Prediction Using Probabilistic Modeling［J］. RNA, 2016, 22(8): 1109-1119.
［5］ SUN L Z, ZHANG D, CHEN S J. Theory and Modeling of RNA Structure and Interactions with Metal ions and Small Molecules［J］. Annual Review of Biophysics, 2017, 46(1): 227-246.
［6］ BAYRAK C S, KIM N, SCHLICK T. Using Sequence Signatures and Kink-turn Motifs in Knowledge-based Statistical Potentials for RNA Structure Prediction［J］. Nucleic Acids Research, 2017, 45(9): 5414-5422.
［7］ MATHEWS D H, TURNER D H. Prediction of RNA Secondary Structure by Free Energy Minimization［J］. Current Opinion in Structural Biology, 2006, 16(3): 270-278.
［8］ ACHAR A, SATROM P. RNA Motif Discovery: a Computational Overview［J］. Biology Direct, 2015, 61(10):1-22.
［9］黄伯虎, 段振华. 量子遗传算法在Web服务选择中的应用［J］. 西安电子科技大学学报, 2010, 37(1): 56-61.
HUANG Bohu, DUAN Zhenhua. Application of the Quantum Genetic Algorithm in Web Services Selection［J］. Journal of Xidian University, 2010, 37(1): 56-61.
［10］ ZUBER J, SUN H, ZHANG X J, et al. 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［J］. Nucleic Acids Research, 2017, 45(10): 6168-6176.
［11］ QI Y. Predicting RNA Secondary Structure Using an Improved BPSO Based on Stem Combination［J］. Applied Mechanics and Materials, 2013, 327: 1551-1554.
［12］ HAN K H, KIM J H. Quantum-inspired Evolutionary Algorithm for a Class of Combinatorial Optimization［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.
［13］ GU J, GU X, GU M. A Novel Parallel Quantum Genetic Algorithm for Stochastic Job Shop Scheduling［J］. Journal of Mathematical Analysis and Applications, 2009, 355(1): 63-81.

[1]	YANG Liying;YANG Shengnan;YUAN Xiguo;GENG Fangge;ZHANG Junying. Analyzing pan-cancer DNA methylation patterns via clustering [J]. Journal of Xidian University, 2018, 45(4): 23-28.
[2]	WEN Honghang;GE Jianhua;XU Tangwen. Low complexity method for PAPR reduction of OFDM signals [J]. J4, 2015, 42(5): 188-193.
[3]	YAN Yi1;2;PEI Chang-xing1;SHI Rui-juan1;HAN Bao-bin1;ZHANG Lei1. Study of quantum communication systems used for free space [J]. J4, 2007, 34(5): 708-711.

RNA secondary structure prediction using the quantum genetic algorithm

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 10