主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
谭光明,冯圣中,孙凝晖.RNA二级结构预测中动态规划的优化和有效并行.软件学报,2006,17(7):1501-1509
RNA二级结构预测中动态规划的优化和有效并行
An Optimized and Efficiently Parallelized Dynamic Programming for RNA Secondary Structure Prediction
投稿时间:2005-06-06  修订日期:2005-12-13
DOI:
中文关键词:  最小自由能  动态规划  计算冗余  负载平衡  加速比
英文关键词:minimum free energy  dynamic programming  redundant calculation  load balancing  speedup
基金项目:Supported bythe National Natural Science Foundation of China under Grant No.60372040(国家自然科学基金);the Knowledge Innovative Project ofthe Chinese Academy of Sceiences under Grant No.KSCX2-SW-233(中国科学院知识创新工程重大项目)
作者单位
谭光明 中国科学院,计算技术研究所,北京,100080
中国科学院,研究生院,北京,100049 
冯圣中 中国科学院,计算技术研究所,北京,100080 
孙凝晖 中国科学院,计算技术研究所,北京,100080 
摘要点击次数: 3911
全文下载次数: 3359
中文摘要:
      基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.
英文摘要:
      RNA secondary structure prediction based on free energy rules remains a major computational method in computational biology. Its basic dynamic programming algorithm needs O(n4) time to calculate the minimum free energy for RNA secondary structure, where n is the length of RNA sequence. There are two variants for handling this problem: either the internal loops are bounded by a maximal size k, giving a time complexity of O(n2×k2), or one uses the trick of Lyngso, which makes use of the rules of loop energies, to reduce time complexity to O(n3) for suboptimal free energy without restriction. Only with additional O(n) space, a new algorithm is proposed to eliminate the redundant calculation in the energy of internal loops and reduce the time complexity to O(n3) with unrestricted loop sizes for optimal free energy. While the optimized algorithm is time consuming, an efficient parallel algorithm with good load balancing in cluster systems is also proposed. The experimental results show that the parallel program achieves reasonable speedups.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利