核糖核苷酸(ribonucleic acid,RNA)作为一类生物大分子,在各种细胞生命过程中扮演着重要的角色,包括遗传信息的表达、传递、基因调控与催化等。与DNA不同,RNA的结构更加复杂多样,这也是RNA具有丰富功能特性的物质基础。首先由于物理实验方法检测RNA空间结构成本较高,其次,仅依靠物理实验无法满足海量的待测序列数据。因此RNA二级结构的算法模拟预测成为一个重要且具有挑战性的课题。并且,在RNA二级结构中有一类由茎区交叉嵌套产生的子结构叫做假结,由于假结被证实在很多RNA催化过程中起到关键的作用,因此近期在RNA结构预测领域越来越受到重视。本文将遗传算法应用到RNA二级结构预测当中,并且包含了两类假结结构,并通过实验测试,验证算法的可用性与有效性。其次针对RNA结构预测的效率问题,提出基于OpenCL的异构并行加速,对串行算法进行改进和优化,分析串行预测算法中可并行的部分,对计算任务进行重新划分,通过CPU+GPU模式进行异构加速,最终通过实验测试对比串行算法与并行算法效率的高低。论文主要工作如下:(1)实现一种改进的遗传算法,相对于传统的遗传算法,改进了遗传操作,使得预测算法更加接近RNA分子二级结构的折叠过程。算法基于最小自由能思想,结合Mathews&Turner和Dirks&Pierce两种能量参数,预测包含H型假结在内的两种假结结构。最终从RNA STRAND数据库中选取的测试集测试获得0.81的阳性预测率、0.79的敏感性。说明算法有效可用,可以作为RNA二级结构分析的参考之一。(2)针对基于遗传算法带假结的RNA二级结构预测低效的问题,提出基于Open CL的异构并行加速算法,首先进行上述串行算法的并行性分析,得到在螺旋区点阵填充及种群迭代进化两个最耗时的阶段可以进行异构加速,然后改进算法过程,在GPU设备上基于Open CL编程框架对上述两个过程进行改进和提升。最终以相同的测试集进行测试,相对于串行算法,改进后的异构并行加速算法平均可获得2.8x倍的加速。有效降低了RNA二级结构预测的耗时,提升了算法模拟预测的效率。