An Effective Exact Algorithm and a New Upper Bound for the Number of Contacts in the Hydrophobic-Polar Two-Dimensional Lattice Model

摘要

Protein Structure Prediction (PSP) is the problem of predicting the three-dimensional native structure of a protein given its primary structure, i.e., the corresponding sequence of amino acids. Different approaches have been proposed to model this problem, and this research explores the prediction of optimal structures using the well studied simplified lattice Hydrophobic and Polar (HP) model—in particular, on the 2D square lattice. We present a twofold result. First, we devise a new upper bound for the number of contacts achievable by an HP sequence, and show that it is in several cases more stringent than the upper bound previously known in literature. Then, we present an innovative algorithm that outperforms the state of the art in exact approaches for the prediction of optimal structures in lattice protein model, for 2D square lattices. The algorithm, called minwalk and based on a heavily pruned exhaustive search, also outperforms the state of the art in non-exact approaches in several cases. Due to this algorithm, it is now possible to prove optimal results in the square 2D lattice, for standard HP sequences of size up to 80 elements, which were only best-known-results previously. Furthermore, we provide the degeneracy (i.e. all optimal solutions) of such benchmark sequences, which was unknown in literature. These results can be a useful tool to foster advances in further research.