Auto-Poietic Algorithm for Multiple Sequence Alignment
Amouda
Venkatesan and Buvaneswari Shanmugham
Centre
for Bioinformatics, Pondicherry University, India
Abstract: The concept of
self-organization is applied to the operators and parameters of genetic algorithm
to develop a novel Auto-poietic algorithm solving a biological problem, Multiple
Sequence Alignment (MSA). The self-organizing crossover operator of the
developed algorithm undergoes a swap and shuffle process to alter the genes of
chromosomes in order to produce better combinations. Unlike Standard Genetic
Algorithms (SGA), the mutation rate of auto-poietic algorithm is not fixed. The
mutation rate varies cyclically based on the improvement of fitness value in
turn, determines the termination point of algorithm. Automated assignment of
various parameter values reduces the intervention and inappropriate settings of
parameters from user without prior the knowledge of input. As an advantage, the
proposed algorithm also circumvents the major issues in standard genetic
algorithm, premature convergence and time requirements to optimize the
parameters. Using Benchmark Alignment Database (BAliBASE) reference multiple
sequence alignments, the efficiency of the auto-poietic algorithm is analyzed.
It is evident that the performance of auto-poietic algorithm is better than SGA
and produces better alignments compared to other MSA tools.
Keywords: Auto-poietic, crossover,
genetic algorithm, mutation, multiple sequence alignment, selection.
Received October 27, 2014; accepted November 29, 2015