Far East Journal of Experimental and Theoretical Artificial Intelligence
Volume 5, Issue 1-2, Pages 1 - 17
(May 2010)
|
|
HYBRID ITERATED LOCAL SEARCH ALGORITHM FOR SOLVING MULTIPLE SEQUENCES ALIGNMENT PROBLEM
Gamil Abdel Azim and Mohamed Ben Othman
|
Abstract:
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 special case of genetic algorithms (GAs). This hybrid evolutionary algorithm works with a population size of two, the probability of crossover and mutation are set to one and the replacement strategy is the replace-worst of the population. Performance of the proposed algorithms is improved by iterated local search technique, which is referred to as 2-opt. We are defining permutation solution’s space corresponding to alignment solution’s space that gives a good application for genetic operations. We are studying scoring function for multiple alignments, related to permutation solution that used as objective function to local search algorithm improvement. It is simple to implement and gives good results. Performance and comparison between the proposed approach and ClustalW are analyzed and the obtained solution qualities are reported. |
| Keywords and phrases: sequence alignment, genetics algorithms, combinatorial optimization |
| Communicated by Shun-Feng Su |
| Number of Downloads: 156 | Number of Views: 674 |
|
