Department of Information Science, The Universiry of Tokyo
Japan Natiomnal Institute of Health
An RNA secondary structure prediction method using a highly parallel computer is reported. We focus on finding thermodynamically stable structures of a single-stranded RNA molecule. Our approach is based on a parallel combinatorial method which calculates the free energy of a molecule as the sum of the free energies of all the possible hydrogen bonds. Most of the conventional prediction methods find only the most stable structure. In contrast, our parallel algorithm finds many highly stable structures at once. The important idea in our algorithm is search-order scheduling. This scheduling helps us find highly stable RNA structures faster, and reduce unnecessary computation.