A Complete and Effective Move Set for Simplified Protein Folding

We present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobic-hydrophilic model. We found these solutions with a generic implementation of tabu search using an apparently novel set of transformation we call pull moves. Our experiments show that our algorithm can find these best solutions in 3 to 14 hours, on average. Pull moves appear quite effective and may also be useful for other local search algorithms for the problem. Additionally, we prove that pull moves are complete; that is, any pair of valid configurations is reachable through a sequence of pull moves. Our implemenation was developed with the Human-Guided Search (HuGS) middleware, which allows rapid development of interactive optimization systems.