基于OpenCL的RNA二级结构预测算法  

Secondary Structure Prediction of RNA Based on OpenCL

作　　者：汪方良 施慧彬[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,江苏南京211100

出　　处：《计算机技术与发展》2017年第9期1-6,共6页Computer Technology and Development

基　　金：国家"973"重点基础研究发展计划项目(2014CB744900)

摘　　要：包含假结的RNA二级结构预测在计算分子生物学中一直是一个重要的研究领域,而预测包含任意类型假结结构已被证明为NP完全问题。为了解决此类问题,在CPU平台上实现了一种改进的遗传算法。该算法可预测包含两类假结结构的RNA序列,敏感性可达到0.775,阳性预测率可达到0.822 5。针对基于遗传算法带假结的RNA二级结构预测低效的问题,提出了基于OpenCL的异构并行加速算法。该算法在分析串行算法并行性的基础上,在种群迭代进化阶段进行异构加速,并基于GPU设备和OpenCL编程框架改进算法过程。为验证所提算法的可行性和有效性,基于相同的测试集进行了实验测试。测试结果表明,相对于串行算法,改进后的异构并行加速算法平均可实现2.72倍的速度提升,有效降低了RNA二级结构预测的耗时,提高了算法模拟预测效率。Predicting RNA secondary structure is an important field in computational molecular biology especially including pseudoknots. However,predicting RNA secondary structure with all kinds of pseudoknots has been proven to be an NP-complete problem. To solve it, an improved genetic algorithm is proposed in CPU platform, which can predict two kinds of pseudoknots. Its sensitivity can reach 0.775 and its positive predictive value can reach 0.822 5. The prediction of RNA secondary structure with pseudoknots based on genetic algo- rithm is inefficient. To solve it, an accelerated algorithm based on OpenCL is presented, which accelerates the period of individual evolu- tion according to the analysis of parallelizability of serial prediction algorithm. Then the algorithm established with GPU based on OpenCL is promoted. The contrast experiments with the same test set have been conducted compared with other algorithms. The experimental re- suits show that the improved heterogeneous parallel algorithm has acquired 2.72 times faster average operation rate than others, reducing the computing time effectively and improving the efficiency of prediction.

关 键 词：RNA二级结构预测 假结 OPENCL 异构计算 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]