Title: Replica Exchange Monte Carlo for Protein Folding in the HP Model
Speaker: Chris Thachuk
Abstract The HP model is commonly adopted in the study of the ab initio protein folding problem. Many algorithms have been proposed to solve problems in both the 2D and 3D HP model. Algorithms for this problem can generally be classified as either primarily based on chain growth or local search, although hybrids and alternatives do exist. In this work we implement and evaluate a local search based algorithm, replica exchange monte carlo (REMC). REMC is an extended ensemble monte carlo algorithm and has demonstrated much success in solving high dimensional problems with many local minima. REMC has been applied in many instances to the off-lattice protein folding problem, however, to the best of the authors knowledge this work is the first to extensively study its use in the HP model. We demonstrate the algorithm as highly effective in the 2D case, outperforming current state-of-the-art algorithms in most benchmark instances, even with loosely tuned parameters. REMC is shown to be competitive, but not dominate in the 3D case. A significant performance increase when combining multiple existing movesets is demonstrated in certain instances. Evidence that REMC can fold sequences which exhibit significant interaction between termini in the structural core relatively easily compared with state-of-the-art algorithms is also presented.