Hybrid Iterated Local Search Algorithm for Solving Multiple Sequences Alignment Problem

G.A. Azim (Saudi Arabia)


Sequence alignment, Genetics algorithms CombinatorialOptimization, Local Search and improvement methods,DNA, Computational molecular biology.


Multiple sequence alignment is one of the important research topics of bioinformatics, and represents an important facet of molecular sequence analysis. Multiple sequence alignment is a natural extension of two sequence alignment. In multiple sequence alignment, it is emphasized to find optimal alignment for a group of sequences. In both cases, all sequences are constituted of residues i.e. nucleotides for DNA/RNA, or amino acids for proteins. The objective is to maximize the similarities between them by adding and shuffling gaps. We propose a hybrid algorithm based on genetic algorithms (GAs). This hybrid evolutionary algorithm works with a population size of two. The probability of crossover and mutation are set as one. Performance of the proposed algorithms is improved by iterated local search technique, which is referred to as 2-Opt. We are defining permutation solution corresponding to alignment solution, and we are studying scoring function for multiple alignments, used as objective function to local search algorithm improvement. It simple to implement and gives good results Performance and comparison of the proposed approach is analyzed and the obtained solution qualities are reported.

Important Links:

Go Back