Spiral search: a hydrophobic-core directed local search for simplified PSP on 3D FCC lattice.
BACKGROUND
Protein structure prediction is an important but unsolved problem in biological science. Predicted structures vary much with energy functions and structure-mapping spaces. In our simplified ab initio protein structure prediction methods, we use hydrophobic-polar (HP) energy model for structure evaluation, and 3-dimensional face-centred-cubic lattice for structure mapping. For HP energy model, developing a compact hydrophobic-core (H-core) is essential for the progress of the search. The H-core helps find a stable structure with the lowest possible free energy.


RESULTS
In order to build H-cores, we present a new Spiral Search algorithm based on tabu-guided local search. Our algorithm uses a novel H-core directed guidance heuristic that squeezes the structure around a dynamic hydrophobic-core centre. We applied random walks to break premature H-cores and thus to avoid early convergence. We also used a novel relay-restart technique to handle stagnation.


CONCLUSIONS
We have tested our algorithms on a set of benchmark protein sequences. The experimental results show that our spiral search algorithm outperforms the state-of-the-art local search algorithms for simplified protein structure prediction. We also experimentally show the effectiveness of the relay-restart.
Institute for Integrated & Intelligent Systems, Griffith University, QLD, Australia. mahmood.rashid@nicta.com.au
Mahmood A
MA
Rashid
M A Hakim
MA
Newton
Md Tamjidul
MT
Hoque
Swakkhar
S
Shatabda
Duc Nghia
DN
Pham
Abdul
A
Sattar
D000465:Algorithms; D000595:Amino Acid Sequence; D057927:Hydrophobic and Hydrophilic Interactions; D008962:Models, Theoretical; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
D011506:Proteins