Technical report detail

An effective exact algorithm and a new upper bound for the number of contacts in the hydrophobic-polar 2D-lattice model

by Emanuele Giaquinta and Laura Pozzi


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 lattice-structures, using the well studied simplified lattice Hydrophobic and Polar (HP) model---in particular, in 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 2-D square lattices. The algorithm, called minwalk and based on a heavily pruned 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.


Technical report 2012/02, November 2012

BibTex entry

@techreport{12effective, author = {Emanuele Giaquinta and Laura Pozzi}, title = {An effective exact algorithm and a new upper bound for the number of contacts in the hydrophobic-polar 2D-lattice model}, institution = {University of Lugano}, number = {2012/02}, year = 2012, month = nov }
Allegati