Self organizing genetic algorithm for multiple sequence alignment

Abstract

Genetic Algorithms (GA) are adaptive search techniques used to solve difficult optimization problem of huge search space in various scientific domains. To solve complex problems in various domains where little is known, GAs can be very useful. The performance of GA is greatly dependent on adjusting its parameters values by the users to reach a better solution for a problem. Unfortunately, conventional GAs needs special attention to choose a suitable set of parameter values which determines the efficiency of the genetic algorithm to perform well for a problem. It is very difficult for a non-specialist user to specify various parameters values for population size, crossover rate, and mutation rate of GA. Although many researches have suggested number of adaptive GAs for adjusting multiple parameters, they require extremely large computation costs and user s intervention. An appropriate selection of parameters and its values makes the algorithm to converge properly in turn producing the best results in an adequate time. Else it runs for a long time before finding a good solution or even it might never be able to find an optimal/ near optimal solution thus lead to premature convergence. This thesis presents a novel algorithm with self-organizing principles applied to Genetic algorithm (SOGA) to eliminate this drawback. Self organization technique automates the genetic algorithm operation on behalf of the user by incorporating the knowledge of parameter selection within the algorithm itself. The validity of the algorithm is illustrated with a NP hard problem; Multiple Sequence Alignment (MSA) which plays an important role in molecular sequence analysis. The alignments made by various operators developed for SOGA are compared with the alignments produced by other standard GA and exiting tools for MSA found to be better.