BioImpacts. 2021;11: 271-279.
doi: 10.34172/bi.2021.37
PMID: 34631489
PMCID: PMC8494253
Scopus ID: 85113810678
  Abstract View: 304
  PDF Download: 212
  Full Text View: 92

Original Research

GADP-align: A genetic algorithm and dynamic programming-based method for structural alignment of proteins

Soraya Mirzaei 1 ORCID logo, Jafar Razmara 1* ORCID logo, Shahriar Lotfi 1

1 Department of Computer Science, Faculty of Mathematics, Statistics, and Computer Science, University of Tabriz, Tabriz, Iran
*Corresponding Author: *Corresponding author: Jafar Razmara, Email: , Email: razmara@tabrizu.ac.ir


Introduction: Similarity analysis of protein structure is considered as a fundamental step to give insight into the relationships between proteins. The primary step in structural alignment is looking for the optimal correspondence between residues of two structures to optimize the scoring function. An exhaustive search for finding such a correspondence between two structures is intractable.
Methods: In this paper, a hybrid method is proposed, namely GADP-align, for pairwise protein structure alignment. The proposed method looks for an optimal alignment using a hybrid method based on a genetic algorithm and an iterative dynamic programming technique. To this end, the method first creates an initial map of correspondence between secondary structure elements (SSEs) of two proteins. Then, a genetic algorithm combined with an iterative dynamic programming algorithm is employed to optimize the alignment.
Results: The GADP-align algorithm was employed to align 10 ‘difficult to align’ protein pairs in order to evaluate its performance. The experimental study shows that the proposed hybrid method produces highly accurate alignments in comparison with the methods using exactly the dynamic programming technique. Furthermore, the proposed method prevents the local optimal traps caused by the unsuitable initial guess of the corresponding residues.
Conclusion: The findings of this paper demonstrate that employing the genetic algorithm along with the dynamic programming technique yields highly accurate alignments between a protein pair by exploring the global alignment and avoiding trapping in local alignments.
Keywords: Bioinformatics, Protein structure alignment, Genetic algorithm, Dynamic programming
First Name
Last Name
Email Address
Security code

Abstract View: 305

Your browser does not support the canvas element.

PDF Download: 212

Your browser does not support the canvas element.

Full Text View: 92

Your browser does not support the canvas element.

Submitted: 03 Feb 2020
Revision: 10 Jun 2020
Accepted: 16 Jun 2020
ePublished: 08 Jul 2020
EndNote EndNote

(Enw Format - Win & Mac)

BibTeX BibTeX

(Bib Format - Win & Mac)

Bookends Bookends

(Ris Format - Mac only)

EasyBib EasyBib

(Ris Format - Win & Mac)

Medlars Medlars

(Txt Format - Win & Mac)

Mendeley Web Mendeley Web
Mendeley Mendeley

(Ris Format - Win & Mac)

Papers Papers

(Ris Format - Win & Mac)

ProCite ProCite

(Ris Format - Win & Mac)

Reference Manager Reference Manager

(Ris Format - Win only)

Refworks Refworks

(Refworks Format - Win & Mac)

Zotero Zotero

(Ris Format - Firefox Plugin)