基于多解并行遗传算法预测RNA二级结构及假结

非编码RNA功能通常与其结构密切相关,准确预测RNA的二级结构有助于揭示RNA的功能。在传统的遗传算法基础上,结合RNA二级结构和假结的特点,提出一种多解并行的遗传算法预测RNA二级结构和假结。首先构建茎区池和初始解集;然后根据RNA二级结构的基本特点建立目标函数、约束函数、自适应度函数和相应的遗传算子,基于初始解集中多条序列—结构模型进行并行遗传迭代,预测最优RNA二级结构;然后在RNA二级结构基础上,使用遗传算法继续进行迭代和筛选,预测含假结的RNA二级结构。实验结果表明,该方法不仅可以解决大规模茎区的组合问题,还可以减少随机性。该方法与常用的预测假结的IPknot方法比较,对单序列RNA的结构预测结果正确率高且稳定。

RNA二级结构预测方法综述

RNA二级结构预测是计算分子生物学中的一个重要领域.本文介绍了RNA二级结构的预测方法,包括该问题的数学模型、主要算法思想以及每种算法对应的软件.在tRNA和RNase P RNA数据库中随机选取了几组样例对目前主要的7种软件进行测试,同时对每种软件的优缺点进行了详细比较.实验证明,当存在同源序列时,Pfold的效果优于其它软件.最后,在总结分析现有算法的基础上探讨了该领域进一步的研究方向.

日新月异的RNA二级结构预测

对RNA结构与功能的研究是当今生物信息学一个非常重要的课题 ,对RNA自身功能的认识在当前已经得到了极大的拓展和深入 ,而研究它更可以作为研究蛋白质结构与功能以及DNA序列中基因信息的突破口 .本文系统介绍了从上世纪 70年代以来发展至今的各类RNA二级结构预测算法 ,从对RNA结构预测方法的追溯和跟踪 ,对当今RNA研究的进展和形势作了一个总结 ,并预测了这一领域未来的研究发展趋势 .

基于CPU-GPU混合计算平台的RNA二级结构预测算法并行化研究

RNA二级结构预测是生物信息学领域重要的研究方向,基于最小自由能模型的Zuker算法是目前该领域最典型使用最广泛的算法之一。本文基于CPU+GPU的混合计算平台实现了对Zuker算法的并行和加速。根据CPU和GPU计算性能的差异,通过合理的任务分配策略,实现二者之间的并行协作计算和处理单元间的负载平衡;针对CPU和GPU的不同硬件特性,对Zuker算法在CPU和GPU上的实现分别采取了不同的并行优化方法,提高了混合加速系统的计算性能。实验结果表明,CPU处理单元在混合系统中承担了14%以上的计算任务,与传统的多核CPU并行方案相比,采用混合并行加速方法可获得15.93的全局加速比;与最优的单纯GPU加速方案相比,可获得16%的性能提升,并且该混合计算方案可用于对其它生物信息学序列分析应用的并行和加速。

基于禁忌遗传算法的RNA二级结构预测

生物RNA二级结构预测是生物信息学领域的一个重要研究问题。近来,研究人员提出应用元启发式算法来预测RNA二级结构。该文提出基于禁忌遗传算法的RNA二级结构预测方法(TGARNA),给出茎区相容性检测改进方法,保留最长茎区构造茎区相容个体,以改善种群性能;同时将禁忌搜索融入遗传操作以防止近亲繁殖,保持种群多样性。仿真实验表明TGARNA算法能够有效预测RNA二级结构。

离散蛙跳算法预测RNA二级结构

针对RNA二级结构预测问题,提出了一种离散蛙跳算法,根据RNA分子折叠的特点,重新定义个体的移动距离和位置,并借鉴粒子群优化算法中的惯性权重加以改进,使算法在空间探索和局部求精间取得了很好的平衡.与同领域中著名的预测软件进行了仿真比较,结果表明新的算法具有较高的预测精度.

一种自适应序列长度的RNA二级结构深度预测方法

RNA二级结构预测是结构生物信息学中的一个重要问题.带假结的RNA二级结构预测,由于复杂的假结结构,更是增加了预测的难度.传统的机器学习方法受限于学习模型的结构,输入特征数目必须固定.大部分方法将不同长度的序列统一截断后进行训练,这不仅导致有用信息丢失,而且并破坏了生物序列完整性.针对该问题提出了一种适应序列长度的深度递归神经网络模型,构造了序列长度自适应模块及训练算法,从而不需要截断.同时,由于实际样本比例不均衡,采用了动态加权方法进行改善.随后,在权威数据集RNA STRAND上与四种优秀方法进行了四组比较实验.实验结果表明,本方法的正确率和M atthew s相关系数比定长LSTM方法分别提高了1. 6%和3. 3%;比其它四种典型方法提高了13. 6%和14. 8%.

使用角色反演句法分析器RNA二级结构的预测

RNA二级结构预测问题是生物信息学的一个研究重点。该文主要利用自然语言理解中句法分析的方法来研究RNA二级结构预测。使用基于角色反演算法建立起来的,采用概率上下文无关文法进行分析的句法分析器,来预测RNA二级结构。结合传统Chart算法分析器和广义LR算法分析器的优点,建立角色反演句法分析器;根据RNA二级结构的构建方法建立相应的概率上下文无关文法;给出对RNA二级结构进行预测的具体实例。

基于局部茎搜索的RNA二级结构预测算法

RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法.但RNA结构中假结的存在使MFE问题理论上成为一个NP-hard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态.根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构.该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构,该算法不仅能显著降低搜索RNA二级结构的时间复杂度,还有助于弥补单纯依赖能量预测RNA二级结构的不足.在多种类型的RNA标准数据集上进行了检验,结果表明,该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率.

CPU/GPU系统上存储高效的RNA二级结构预测算法

通过建立映射变换函数来改进基于最小自由能的RNA二级结构预测计算模型,分析证明了改进后的计算模型与原计算模型的等价性,利用改进后的计算模型使得GPU每个warp线程束内的线程并行计算矩阵元素时其所需的数据处于全局存储器同一行中,以支持直接并行读取矩阵元素,显著地减少多线程并行访问全局存储器的次数;充分利用GPU纹理存储器、共享存储器及常量存储器,以减少查找表的时间;设计实现多核CPU/单GPU系统、多核CPU/多GPU系统上存储高效的RNA二级结构预测并行算法.实验结果表明,与已有的RNA二级结构预测算法相比,本文提出的算法效率更高.

基于CUDA对RNA二级结构预测的并行研究

为解决长链RNA二级结构预测面临的计算压力,分析了当前基于最小自由能预测RNA二级结构的相关串行、并行算法,提出了一种基于CUDA(compute unified device architecture)编程模型的并行加速算法。在实现时充分利用了支持CUDA编程模型的GPU(graphic processing unit)设备中的共享存储器、常量存储器等硬件,对RNA二级结构预测算法中的动态规划进行了有效的并行。实验结果表明,在支持CUDA编程模型的GPU上实现的并行程序,获得了与已有的串行、并行算法相同的准确度,同时运行速度更快。

包括假结的RNA二级结构茎区组合预测新算法

提出了RNA茎区组合最优能的概念,给出了RNA茎区相容定义,利用相容矩阵与迭代矩阵以求出具有全局最大最优能的RNA茎区组合,建立了一种能够预测带假结的RNA二级结构的新方法。通过选取PseudoBase中的RNA序列,将预测得到的RNA二级结构与数据库上提供的RNA二级结构进行比较,同时用pknotsRG软件运行同样的数据与本方法得到的RNA二级结构进行比较,NGF-L2和NGF-H1的最好的敏感性、特异性均达到100%。试验结果与分析数据表明,本方法可靠、有效,具有较高的准确率,可以预测假结结构,尤其是tRNA类型的序列执行起来速度较快。

基于混合蚁群遗传算法的RNA二级结构预测

RNA二级结构预测是生物信息学的重要研究领域。本文提出一种新的基于混合蚁群遗传算法的RNA二级结构预测方法。充分利用茎区和茎区之间的关系信息和累积的信息,通过蚁群算法产生初始种群和新的个体,进而替换遗传算法中的变异算子。构造蚁群算法中的启发式信息、初始信息素矩阵、下一茎区的选取规则和信息素的更新机制,给出遗传算法中交叉算子的交叉策略。最后通过测试已知二级结构的RNA序列,实验结果表明,该方法相对于遗传算法不仅节省程序运行的时间,而且可提高预测的准确性。

基于启发式算法预测含假结RNA二级结构的研究进展

RNA二级结构的预测算法研究已有近40年的发展历程,研究假结也将近30年的历史。在此期间,RNA二级结构的预测算法取得了很大进步,但假结预测的正确率依然偏低。其中启发式算法能较好地处理复杂假结,使其成为率先解决假结预测难题可能性最大的算法。迄今为止,未见系统地专门总结预测假结的各种启发式算法及其优点与缺点的报道。本文详细介绍了近年来国际上流行的贪婪算法、遗传算法、ILM算法、HotKnots算法以及FlexStem算法等五种算法,并总结分析了每种算法的优点与不足,最后提出在未来一段时期内,利用启发式算法提高假结预测准确度应从建立更完善的假结模型、加入更多影响因素、借鉴不同算法的优势等方面入手。为含假结RNA二级结构预测的研究提供参考。

多目标遗传算法的含假结RNA二级结构预测

假结是RNA中一种重要的结构,由于建模的困难导致它更难被预测。通过碱基之间的配对概率来预测含假结RNA二级结构的Prob Knot算法具有很高的精度,但该算法仅用了配对概率作为预测依据,导致阴性配对大量出现,因此精度中的特异性较低。实验结合Prob Knot算法中碱基配对概率模型,通过使用多目标遗传算法,从而提高预测含假结RNA二级结构的特异性,以此促进总体精度的提高。实验过程中,首先计算出每个碱基成为单链的概率,作为新增的预测依据,然后使用遗传算法对RNA二级结构进行交叉、变异和迭代,最后得到Pareto最优解,进一步得出最高的最大期望精度。实验结果表明,在使用的RNA案例中,采用该方法比现有方法精度平均提高约4%。

基于进化神经网络的RNA二级结构预测方法

本文提出了一种基于进化神经网络预测RNA二级结构的方法.该方法利用进化算法优化了神经网络结构和权值,改善了传统BP人工神经网络容易陷入局部最优等缺陷.实验结果表明该算法能够获得一个最优结构和权值的神经网络,利用该网络去预测不带伪结的RNA二级结构能获得理想的效果,敏感性和相关系数都有所提升,证明了该改进算法的可行性.

基于FPGA的存储优化的细粒度并行Zuker算法加速器研究

RNA二级结构预测是生物信息学领域重要的研究方向,基于最小自由能模型的Zuker算法是目前该领域最典型使用最广泛的算法之一.基于FPGA平台实现了一种细粒度的并行Zuker算法,采用按矩阵列循环划分的任务分配策略实现了处理单元间的负载平衡;采用数据预取、滑动窗口和数据传递流水线实现了处理单元间的数据重用;采用曲线拟合、离散点赋值和地址空间压缩编码等策略减少了约85%的自由能参数存储需求.在单片FPGA上集成了由20个PE构成的主从多PE线性阵列,实验结果表明与运行在AMD四核9650处理器上的ViennaRNA-1.6.5程序相比,可获得超过18倍的加速效果,并且FPGA加速器功耗仅为通用微处理器平均功耗的1/5.

基于FPGA的细粒度并行CYK算法加速器设计与实现

基于随机上下文无关文法(SCFG)理论模型进行RNA二级结构预测是目前采用计算方法研究RNA二级结构的一种重要途径.由于基于SCFG模型的标准结构预测算法(Coche-Younger-Kasami,CYK)巨大的时空复杂度,对CYK算法进行加速成为计算生物学领域一个极具挑战性的热点问题.CYK的并行性能受限于算法多维度、非一致性的数据依赖关系和较低的计算/通信比,现有的基于通用微处理器结构的大规模并行处理方案不能获得令人满意的加速效果,并且大规模并行计算机系统硬件设备的购置、使用、日常维护的成本高昂,其适用性受到诸多限制.文中在深入分析CYK算法计算特征的基础上,基于FPGA平台提出并实现了一种细粒度的并行CYK算法.设计采用了对三维动态规划矩阵"按区域分割"和"逐层按列并行处理"的计算策略实现了多个处理单元间的负载均衡;采用数据预取、滑动窗口和数据传递流水线实现处理单元间的数据重用,有效解决了计算和通信间的平衡问题;设计了一种类似脉动阵列(systolic-like array)结构的主从多PE并行计算阵列,并在目前最大规模的FPGA芯片(Xilinx XC5VLX330)上成功集成了16个处理单元(processing elements),实验结果表明作者提出的CYK算法加速器结构具备良好的可扩展性.当RNA序列长度为959bps,CM模型状态数为3145时,与运行在Intel双核E5200 2.5GHzCPU、2.0GB主存通用计算上的Infernal-1.0软件相比,可获得超过14倍的加速效果.配置一个FP-GA算法加速器的通用计算平台的综合处理性能与包含20个Intel-Xeon CPU的PC集群相当,而硬件成本仅为后者的20%,系统功耗不到后者的10%.

基于OpenCL大规模种群并行遗传算法

为了提高RNA二级结构预测的准确率和加速遗传算法,提出基于OpenCL大规模种群并行遗传算法。通过研究遗传算法中潜在的并行性,以Acer TMP246M-MG-5086为实验平台,先在CPU中实现遗传算法,再使用OpenCL技术在GPU中实现大规模种群并行遗传算法。测试结果表明,并行遗传算法对于RNA二级结构预测的准确率平均提高了约49.88%,使用GPU平均加速比为9.76x。

基于茎区的动态规划算法的核糖核酸二级结构预测

结合传统动态规划算法和组合优化算法在二级结构预测的优势,提出了一种以茎区为最小结构单元的新的动态规划算法。对于给定的RNA序列,首先得到所有可能的茎区集合,采用环依赖的方式计算二级结构的能量,通过茎区动态规划算法递归得到能量最优的二级结构,最后选取数据库中不同长度的已知二级结构的RNA序列进行测试。结果表明,该算法在特异性、敏感性和马休兹参数方面均优于遗传算法,在计算复杂性方面低于传统的动态规划算法。