Permutation-based RNA secondary structure prediction via a genetic algorithm

This paper presents new results with a permutation-based genetic algorithm (GA) to predict the secondary structure of RNA molecules. More specifically, the proposed algorithm predicts which canonical base pairs forms hydrogen bonds and builds helices, also known as stems. We discuss a GA where a permutation is used to encode the secondary structure of RNA molecules. We have tested RNA sequences of lengths 76, 210, 681, and 785 nucleotides over a wide variety of operators and parameter settings and focus on discussing in depth the results with two crossover operators asymmetric edge recombinations (ASERC) and symmetric edge recombination (SYMERC) that have not been analyzed in this domain previously. We demonstrate that the keep-best reproduction (KBR) operator has similar benefits as in the travelling salesman problem (TSP) domain. We also compare the results of the permutation-based GA with a binary GA, demonstrating the benefits of the newly proposed representation.