The mathematical model and optimistic algorithm of two protein structures alignment

Protein structure alignment is one of the most important computational problems in molecular biology. From the viewpoint of computational complexity, a pairwise structure alignment is a NP-hard problem. In this paper, based on the discrepancy of two proteins, we define the structure alignment as a mixed integer-programming (MIP) problem with the simpler form and prove the existence of optimal solution. The optimal alignment is achieved by incorporating improved complete information set method used to modify the score matrix into iterative double dynamic programming algorithm. Convergence of algorithm is proved. A number of benchmark examples are tested. The results show that our model and approach are general and improve computational efficiency as well as quality of the structure alignment.