Optimization of an RNA folding algorithm for parallel architectures

摘要

In this paper we describe parallel implementations of a dynamic programming algorithm for predicting ribonucleic acid(RNA)secondary structure based on energy minimization in high performance computers. The computations in the prediction algorithm. The compu- tation ordering and the data placement dictate the performance of the algorithm. Only the diagonal ordering, which starts with short fragments and progresses to successively greater fragments in length, out of three possible computation orderings can take full advantage of the advanced architectures discussed in this study.