title: On lattice protein structure prediction revisited.
abstract: Protein structure prediction is regarded as a highly challenging problem both for the biology and for the computational communities. In recent years, many approaches have been developed, moving to increasingly complex lattice models and off-lattice models. This paper presents a Large Neighborhood Search (LNS) to find the native state for the Hydrophobic-Polar (HP) model on the Face-Centered Cubic (FCC) lattice or, in other words, a self-avoiding walk on the FCC lattice having a maximum number of H-H contacts. The algorithm starts with a tabu-search algorithm, whose solution is then improved by a combination of constraint programming and LNS. The flexible framework of this hybrid algorithm allows an adaptation to the Miyazawa-Jernigan contact potential, in place of the HP model, thus suggesting its potential for tertiary structure prediction. Benchmarking statistics are given for our method against the hydrophobic core threading program HPstruct, an exact method which can be viewed as complementary to our method.
authors.affiliation: Biology Department, Boston College, Higgins 355, 140 Commonwealth Avenue, Chestnut Hill, MA 02467, USA. ivan@bc.edu
authors.forename: Ivan
authors.initials: I
authors.lastname: Dotu
authors.forename: Manuel
authors.initials: M
authors.lastname: Cebrián
authors.forename: Pascal
authors.initials: P
authors.lastname: Van Hentenryck
authors.forename: Peter
authors.initials: P
authors.lastname: Clote
mesh_terms: D000465:Algorithms; D057927:Hydrophobic and Hydrophilic Interactions; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins