Load Balancing Algorithm in Cluster-based RNA secondary structure Prediction

RNA secondary structure prediction remains one of the most compelling, yet elusive areas of computational biology. Many computational methods have been proposed in an attempt to predict RNA secondary structures. A popular dynamic programming (DP) algorithm uses a stochastic context-free grammar to model RNA secondary structures, its time complexity is O(N⁴) and spatial complexity is O(N³ ), where N is the length of sequences. In this paper, a parallel algorithm, which is time-wise and space-wise optimal with respect to the usual sequential DP algorithm, can be implemented using O(N⁴/P) time and O(N³/P) space in cluster, where P is the number of processors. High efficient utilization of processors and good load balancing are important to the performance of parallel algorithms in cluster systems. Two parallel DP algorithms, which have different mappings of the DP matrix to processors, are evaluated concerning running time. As experiments show, dynamic mapping of DP matrix can achieve better load balancing than the static and improve the efficiency of processors. Thus, the dynamic mapping algorithm is faster and gets better speedups