Optimization and Performance Analysis of a Massively Parallel Dynamic Programming Algorithm for Rna Secondary Structure Prediction

Abstract

An optimized and parallelized form of a dynamic pro gramming algorithm capable of generating optimal and suboptimal RNA secondary structures is pre sented. Implementation of this algorithm on a MasPar MP-2 with 16K processors is shown to perform ex tremely well for very large nucleic acid sequences such as HIV (AIDS) and Rhinovirus (common cold). These sequences are, respectively, 9,128 and 7,208 nu cleotides in length. By taking advantage of the parallel nature of MasPar and also optimizing the communica tion requirements the implementation essentially re duced the algorithm from order O(n³) to 0(n²). This reduction in complexity enables us to fold large RNA sequences in reasonable amounts of time. This capa bility has proven to be a valuable tool in studying the molecular structure and biological function of mole cules this large.