Spiral search: a hydrophobic-core directed local search for simplified PSP on 3D FCC lattice

BMC Bioinformatics

Proceedings

Md Tamjidul Hoque¹  Mahmood A Rashid²  Swakkhar Shatabda²  MA Hakim Newton²  Duc Nghia Pham²  Abdul Sattar² 

[1] Computer Science, University of New Orleans, USA;Institute for Integrated & Intelligent Systems, Griffith University, QLD, Australia;Queensland Research Lab, National ICT Australia, QLD, Australia;

关键词: Local Search;    Free Energy;    Hydrophobic Amino Acid;    Local Search Algorithm;    Relative Improvement;   

DOI  :  10.1186/1471-2105-14-S2-S16

来源: Springer

【 摘 要 】

BackgroundProtein 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.ResultsIn 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.ConclusionsWe 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.

【 授权许可】

CC BY   
© Rashid et al.; licensee BioMed Central Ltd. 2013