RNA二级结构预测中动态规划的优化和有效并行

An Optimized and Efficiently Parallelized Dynamic Programming for RNA Secondary Structure Prediction

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2k2)算法;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（n^2×k^2）, or one uses the trick of Lyngso, which makes use of the rules of loop energies, to reduce time complexity to O（n^3） 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（n^3） 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.