Optimization and performance analysis of a massively-parallel dynamic programming algorithm for RNA secondary structure prediction

An optimized and parallel form of a dynamic programming algorithm capable of generating optimal and suboptimal RNA secondary structures is presented, Implementation of this algorithm on a MasPar MP-2 with 16K processors is shown to perform extremely well for very large nucleic acid sequences such as HIV (AIDS) and Rhinovirus (common cold). These sequences are, respectively, 9, 128 and 7, 208 nucleotides in length. By taking advantage of the parallel nature of MasPar and also optimizing the communication requirements the implementation essentially reduced the algorithm from order O(n³) to O(n²). This reduction in complexity enables us to fold large RNA sequences in reasonable amounts of time. This capability has proven to be a valuable tool in studying the molecular structure and biological function of molecules this large.