| 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.
|