| 本文已被：浏览 5435次 下载 6828次 |
码上扫一扫！ |
|
|
| RNA二级结构预测中动态规划的优化和有效并行 |
|
谭光明1,2, 冯圣中1, 孙凝晖1
|
|
1.中国科学院,计算技术研究所,北京,100080;2.中国科学院,研究生院,北京,100049
|
|
| 摘要: |
| 基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比. |
| 关键词: 最小自由能 动态规划 计算冗余 负载平衡 加速比 |
| DOI： |
| 分类号: |
| 基金项目: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(中国科学院知识创新工程重大项目) |
|
| An Optimized and Efficiently Parallelized Dynamic Programming for RNA Secondary Structure Prediction |
|
TAN Guang-Ming,FENG Sheng-Zhong,SUN Ning-Hui
|
| Abstract: |
| 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. |
| Key words: minimum free energy dynamic programming redundant calculation load balancing speedup |
