Genetic algorithms for stochastic context-free grammar parameter estimation

by 1979- Tariman, Kaan

Stochastic grammar models for biological sequences have been extensively used in secondary structure prediction and profiling for structural homology recognition. A pertinent issue is, given training RNA sequences, how to estimate the stochastic parameters associated with the rules in the grammar efficiently and accurately. In particular, the existing algorithms for parameter estimation, such as Inside-Outside, have local maxima and time complexity problems. We introduce a genetic algorithm method to solve the parameter estimation problem. Being global optimization methods, genetic algorithms do not suffer from the locality problem and they are scalable and flexible. The model uses an evaluation function that calculates the maximum likelihood to generate a sequence given a parameter set of a grammar. Our experiments with the implemented algorithm demonstrate its effectiveness in parameter estimation for specific grammar models based on both simple RNA structures and tRNA sequences.