A Replica Exchange Monte Carlo Algorithm for Protein Folding in the HP Model

Background: The ab initio protein folding problem consists of predicting protein tertiary structurefrom a given amino acid sequence by minimizing an energy function; it is one of the most importantand challenging problems in biochemistry, molecular biology and biophysics. The ab initio proteinfolding problem is computationally challenging and has been shown to be -hard even whenconformations are restricted to a lattice. In this work, we implement and evaluate the replicaexchange Monte Carlo (REMC) method, which has already been applied very successfully to morecomplex protein models and other optimization problems with complex energy landscapes, incombination with the highly effective pull move neighbourhood in two widely studied HydrophobicPolar (HP) lattice models.Results: We demonstrate that REMC is highly effective for solving instances of the square (2D)and cubic (3D) HP protein folding problem. When using the pull move neighbourhood, REMCoutperforms current state-of-the-art algorithms for most benchmark instances. Additionally, weshow that this new algorithm provides a larger ensemble of ground-state structures than theexisting state-of-the-art methods. Furthermore, it scales well with sequence length, and it findssignificantly better conformations on long biological sequences and sequences with a provablyunique ground-state structure, which is believed to be a characteristic of real proteins. We alsopresent evidence that our REMC algorithm can fold sequences which exhibit significant interactionbetween termini in the hydrophobic core relatively easily.Conclusion: We demonstrate that REMC utilizing the pull move neighbourhood significantlyoutperforms current state-of-the-art methods for protein structure prediction in the HP model on2D and 3D lattices. This is particularly noteworthy, since so far, the state-of-the-art methods for2D and 3D HP protein folding – in particular, the pruned-enriched Rosenbluth method (PERM) and,to some extent, Ant Colony Optimisation (ACO) – were based on chain growth mechanisms. Tothe best of our knowledge, this is the first application of REMC to HP protein folding on the cubiclattice, and the first extension of the pull move neighbourhood to a 3D lattice