A Hybrid Local Search for Simplified Protein Structure Prediction
This addresses the issue of search stagnation in protein structure prediction for computational biology, but it is incremental as it builds on existing local search methods.
The paper tackled the problem of protein structure prediction stagnation in local search algorithms by restructuring segments of conformations with compact hydrophobic cores, achieving significantly better results than state-of-the-art methods on standard benchmark proteins.
Protein structure prediction based on Hydrophobic-Polar energy model essentially becomes searching for a conformation having a compact hydrophobic core at the center. The hydrophobic core minimizes the interaction energy between the amino acids of the given protein. Local search algorithms can quickly find very good conformations by moving repeatedly from the current solution to its "best" neighbor. However, once such a compact hydrophobic core is found, the search stagnates and spends enormous effort in quest of an alternative core. In this paper, we attempt to restructure segments of a conformation with such compact core. We select one large segment or a number of small segments and apply exhaustive local search. We also apply a mix of heuristics so that one heuristic can help escape local minima of another. We evaluated our algorithm by using Face Centered Cubic (FCC) Lattice on a set of standard benchmark proteins and obtain significantly better results than that of the state-of-the-art methods.