RNA structure as permutation: A GA approach comparing different genetic sequencing operators

This paper presents a genetic algorithm (GA) to predict the secondary structure of RNA molecules, where the secondary structure is encoded as a permutation. More specifically the proposed algorithm predicts which specific canonical base pairs will form hydrogen bonds and build helices, also known as stem loops. Since RNA is involved in both transcription and translation and also has catalytic and structural roles in the cell, knowing its structure is of fundamental importance since it will determine the function of the RNA molecule. We discuss results on RNA sequences of lengths 76, 681, and 785 nucleotides and present several improvements to our algorithm. We show that the Keep-Best Reproduction operator has similar benefits as in the TSP domain. In addition, a comparison of several crossover operators is provided, demonstrating that CX, an operator that is marginal in the TSP domain, performs very well in the RNA folding domain.