A permutation-based genetic algorithm for the RNA folding problem: a critical look at selection strategies, crossover operators, and representation issues.
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 stems. Since RNA is involved in both transcription and translation and also has catalytic and structural roles in the cell, determining the structure of RNA is of fundamental importance in helping to determine RNA function. We introduce a GA where a permutation is used to encode the secondary structure of RNA molecules. We discuss results on RNA sequences of lengths 76, 210, 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 traveling salesman problem domain. In addition, a comparison of several crossover operators is provided. We also compare the results of the permutation-based GA with a binary GA, demonstrating the benefits of the newly proposed representation.
Wiese
Kay C
KC
Information Technology, Simon Fraser University, 2400 Central City, 10153 King George Highway, Surrey, BC, Canada V3T 2W1. wiese@sfu.ca
Glen
Edward
E
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*
D012313:RNA