GADP_align: A hybrid method for structural alignment of proteins using genetic algorithm and dynamic programming techniques

Structural comparison and alignment of proteins is one of the fundamental techniques in protein structure analysis. The major step in structural alignment is a search to find the optimal set of correspondence between two structures and optimize the scoring function. One of the most commonly used approaches is an initial guess of the rigid-body transformation followed by an iterative dynamic programming algorithm. These methods use dynamic programming over several initial pairwise alignments, and then, choose the alignment with the best score as the final output. Dynamic programming is an example of the optimization methods that can be successfully combined with metaheuristics such as genetic algorithm. In this paper, we have proposed a hybrid algorithm, namely GADP-align, for pairwise protein structure alignment by combining a genetic algorithm with an iterative dynamic programming. The experimental study shows that the proposed hybrid method produces highly accurate alignments in comparison with the methods using exactly the dynamic programming technique. Further, it is shown that the proposed method prevents the local optimal traps caused by the bad initial guess of the residue equivalences.

Keywords:

Protein structure alignment , genetic algorithm , dynamic programming , bioinformatics