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

Abstract

Abstract A massively parallel Genetic Algorithm (GA) has been applied to RNA sequence folding on three different computer architectures. The GA, an evolution-like 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 population in parallel. The algorithm was originally designed and developed for a 16384 processor SIMD (Single Instruction Multiple Data) MasPar MP-2. More recently it has been adapted to a 64 processor MIMD (Multiple Instruction Multiple Data) SGI ORIGIN 2000, and a 512 processor MIMD CRAY T3E. The MIMD version of the algorithm raises issues concerning RNA structure data-layout and processor communication. In addition, the effects of population variation on the predicted results are discussed. Also presented are the scaling properties of the algorithm from the perspective of the number of physical processors utilized and the number of virtual processors (RNA structures) operated upon. Contact: bshapiro@ncifcrf.gov; jcwu@ncifcrf.gov; bengalid@ncifcrf.gov; mark.potts@ieee.org * To whom correspondence should be addressed. 4 Current address: HPC Applications Inc., 10080 Old Frederick Road, Ellicott City, MD 21042, USA.