A replica exchange Monte Carlo algorithm for protein folding in the HP model.

Area of Science:

• Biophysics
• Computational Biology
• Biochemistry

Background:

• The ab initio protein folding problem aims to predict a protein's 3D structure from its amino acid sequence, a computationally intensive challenge.
• This problem is known to be NP-hard, even with simplified lattice models, necessitating advanced computational approaches.

Purpose of the Study:

• To implement and evaluate the Replica Exchange Monte Carlo (REMC) method for ab initio protein folding.
• To assess the effectiveness of REMC combined with the pull move neighborhood in Hydrophobic Polar (HP) lattice models.

Main Methods:

• Utilized the Replica Exchange Monte Carlo (REMC) method.
• Integrated the pull move neighborhood strategy within the REMC framework.
• Applied the combined method to 2D (square) and 3D (cubic) Hydrophobic Polar (HP) lattice models.

Main Results:

• REMC with the pull move demonstrated high effectiveness in solving 2D and 3D HP protein folding problems.
• Outperformed current state-of-the-art algorithms for most benchmark instances, yielding a larger ensemble of ground-state structures.
• Showcased good scalability with sequence length and superior performance on long biological sequences and those with unique ground-state structures.

Conclusions:

• REMC with the pull move neighborhood significantly surpasses existing state-of-the-art methods for HP protein folding on 2D and 3D lattices.
• This approach offers a novel alternative to chain growth mechanisms like PERM and ACO.
• Represents the first application of REMC to HP protein folding on a cubic lattice and the first extension of the pull move to a 3D lattice.