The massively parallel genetic algorithm for RNA folding: MIMD implementation and population variation

A massively parallel Genetic Algorithm (GA) has been applied to RNA sequenc e folding on three different computer architectures. The GA, an evolution-l ike algorithm that is applied to a large population of RNA structures based on a pool of helical stems derived from an RNA sequence, evolves this popu lation in parallel. The algorithm was originally designed and developed for a 16 384 processor SIMD (Single Instruction Multiple Data) MasPar MP-2. Mo re recently it has been adapted to a 64 processor MIMD (Multiple Instructio n Multiple Data) SGI ORIGIN 2000, and a 512 processor MIMD GRAY T3E. The MI MD version of the algorithm raises issues concerning RNA structure data-lay out and processor communication. In addition, the effects of population var iation on the predicted results are discussed. Also presented are the scali ng properties of the algorithm from the perspective of the number of physic al processors utilized and the number of virtual processors (RNA structures ) operated upon.