A new effective algorithm for protein chain lattice fit problem

Protein structure prediction (PSP) problem deals with finding the three dimensional native structure of a protein. Details of a protein´s atomic complexity and unknown energy function make the problem harder. To solve the problem, numerous attempts have been tried by the researchers in the recent years. One of the approaches is using lattice model for simplification. The advantage of lattice model is discretization of the space which enables faster heuristic search algorithms to be used. However, one of the principal concern is the selection of proper lattice to model the protein structures. A number of lattices have been used and proposed in the literature of protein chain lattice fit (PCLF) problem. In PCLF problem, a three dimensional fold of a protein chain considering the coordinates of C-α atoms is mapped to lattice as its vertices and target is to make a protein lattice model similar to its native structure. In this paper, we proposed a two stage algorithm for PCLF problem using KW (knights walk) lattice model. We first use chain growth algorithm to map the C-α carbon in lattice and found very close lattice fit with lower dRMSD. In the second stage, we apply a local search algorithm using a novel operator diagonal move. On a standard set of benchmark protein structures, our algorithm was able to find improvement over other lattices used by the state-of-the-art algorithms.