A genetic algorithm to search for optimal and suboptimal RNA secondary structures

Genetic algorithms are a search method used in solving problems by selection, recombination and mutation of tentative solutions, until the better ones are achieved. They are very efficient when the 'building block' hypothesis is effective for the solutions, which means that a better solution can be obtained by assembling short 'motifs' or 'schemata' that can be retrieved in some other worse solutions. The additive nature of the secondary structure free energy rules suggests the validity of this hypothesis, and therefore the likely power of a genetic algorithm approach to search for RNA secondary structures. We describe in detail an original genetic algorithm specific for this problem. The sharing function used to obtain differentiated solutions is also described. It results in a greater effectiveness of the algorithm in retrieving a large number of suboptimal RNA foldings besides the optimal one. RNA sequences of different length are used to test the method. The PSTV viroid sequence has been studied.