DGA: Decomposition with genetic algorithm for multiple sequence alignment

Multiple sequence alignment is one of the most important issues in molecular biology as it plays an important role such as in life saving drug design. In this paper, we divide given sequences into two or more subsequences and then combine them together in order to find better multiple sequence alignments by applying a new GA based approach to the combined sequences. We also introduce new ways of generating an initial population and of applying the genetic operators. We have carried out experiments for the BAliBASE benchmark database using the sum of pair objective function with the PAM250 score matrix. To evaluate our proposed approach, we have compared with well known methods such as T-Coffee, MUSCLE, MAFFT and ProbCons. The experimental results show that better multiple sequence alignments may be obtained with higher number of divisions, however the computation time increases with the number of decompositions. The overall performance of the proposed Decomposition with GA (DGA) method is better than the existing methods and the GA method (without decompositions).