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

RNA secondary structure prediction using the quantum genetic algorithm

作　　者：刘阳 李佳桥[4] 王凡 王增斌 石莎 LIU Yang;LI Jiaqiao;WANG Fan;WANG Zengbin;SHI Sha(School of Cyber Security,Univ.of the Chinese Academy of Sciences,Beijing 100049,China;Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;National Computer Network Emergency Response Technical Coordination Center,Beijing 100029,China;School of Telecommunications Engineering,Xidian Univ.,Xi＇an 710071,China;Quantah Systems Sci.~Tech.Stockholdings Ltd.Beijing 100095,China;School of Life Sciences and Technology,Xidian Univ.,Xi＇an 710071,China)

机构地区：[1]中国科学院大学网络空间安全学院,北京100049 [2]中国科学院信息工程研究所,北京100093 [3]国家计算机网络与应急技术处理协调中心,北京100029 [4]西安电子科技大学通信工程学院,陕西西安710071 [5]北京量子体系科技股份有限公司,北京100095 [6]西安电子科技大学生命科学技术学院,陕西西安710071

出　　处：《西安电子科技大学学报》2018年第4期112-117,共6页Journal of Xidian University

基　　金：国家自然科学基金资助项目(61502376;61771377;61301172);陕西省国际科技合作与交流计划资助项目(2015KW-037;2017KW-003)

摘　　要：由于基于最小自由能模型的传统算法复杂度高且搜索效率低,故利用量子遗传算法提出了一种新的核糖核酸二级结构的预测算法.该算法将种群信息加载到量子比特上完成初始化,通过量子酉变换(量子逻辑门)实现种群的更新与演化,借助于量子计算的并行性优势使得核糖核酸二级结构预测所需种群规模相对经典遗传算法大为减少,同时还具有更强的搜索预测能力.基于国际核糖核酸标准数据库提供的序列进行了量子模拟实验计算,结果表明,在种群规模为经典遗传算法20%的条件下,该算法预测准确率仍优于经典遗传算法,且所需的进化轮数也得到了明显降低.Due to the high complexity and low search efficiency of the traditional algorithm based on the minimum free energy model,aquantum 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.

关 键 词：量子计算 量子算法 量子模拟 核糖核酸 二级结构预测 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]