Paper Info
Title
An effective exact algorithm and a new upper bound for the number of contacts in the hydrophobic-polar two-dimensional lattice model.
Abstract
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.
Year
DOI
Venue
2013
10.1089/cmb.2012.0266
JOURNAL OF COMPUTATIONAL BIOLOGY
Keywords
Field
DocType
algorithms,automata,strings
Protein structure prediction,Square lattice,Exact algorithm,Lattice (order),Brute-force search,Upper and lower bounds,Algorithm,Lattice protein,Lattice model (finance),Mathematics
Journal
Volume
Issue
ISSN
20.0
8
1066-5277
Citations 
PageRank 
References 
3
0.40
9
Authors
2
Name
Order
Citations
PageRank
Emanuele Giaquinta110011.28
Laura Pozzi2132.60