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

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.