Wang-Landau sampling in face-centered-cubic hydrophobic-hydrophilic lattice model proteins

Finding the global minimum-energy structure is one of the main problems of protein structure prediction. The face-centered-cubic (fcc) hydrophobic-hydrophilic (HP) lattice model can reach high approximation ratios of real protein structures, so the fcc lattice model is a good choice to predict the protein structures. The lacking of an effective global optimization method is the key obstacle in solving this problem. The Wang-Landau sampling method is especially useful for complex systems with a rough energy landscape and has been successfully applied to solving many optimization problems. We apply the improved Wang-Landau (IWL) sampling method, which incorporates the generation of an initial conformation based on the greedy strategy and the neighborhood strategy based on pull moves into the Wang-Landau sampling method to predict the protein structures on the fcc HP lattice model. Unlike conventional Monte Carlo simulations that generate a probability distribution at a given temperature, the Wang-Landau sampling method can estimate the density of states accurately via a random walk, which produces a flat histogram in energy space. We test 12 general benchmark instances on both two-dimensional and three-dimensional (3D) fcc HP lattice models. The lowest energies by the IWL sampling method are as good as or better than those of other methods in the literature for all instances. We then test five sets of larger-scale instances, denoted by the S, R, F90, F180, and CASP target instances on the 3D fcc HP lattice model. The numerical results show that our algorithm performs better than the other five methods in the literature on both the lowest energies and the average lowest energies in all runs. The IWL sampling method turns out to be a powerful tool to study the structure prediction of the fcc HP lattice model proteins.

Figure 1

Unit of the 2D fcc HP lattice model, where the six basis vectors are shown and grid point $O$ has six neighbors.

Figure 2

Unit of the 3D fcc HP lattice model, where the 12 basis vectors are shown and grid point $O$ has 12 neighbors.

Figure 3

Example of the single-point pull moves on the 2D fcc HP lattice model. Closed and open circles indicate the hydrophobic and hydrophilic amino acids, respectively. If position $A$ is free, then amino acid 5 can be placed at $A$ and a pull move in (a) can be executed, where amino acid 6 is moved to the position of amino acid 5 and then a valid conformation [indicated in (b)] is obtained.

Figure 4

Example of parallel pull moves on the 2D fcc HP lattice model. Closed and open circles indicate the hydrophobic and hydrophilic amino acids, respectively. If positions $A$ and $B$ are free [see (a)], then amino acids 4 and 5 can be placed at their adjacent parallel positions $A$ and $B$. Then, to obtain a valid conformation, on the left side of amino acid 4, amino acid 3 is moved to the position of amino acid 4, 2 to 3, and 1 to 2 and on the right side of amino acid 5, amino acid 6 is moved to the position of amino acid 5 and 7 to 6 [indicated in (b)].

Figure 5

Example of tilted pull moves on the 2D fcc HP lattice model. Closed and open circles indicate the hydrophobic and hydrophilic amino acids, respectively. If positions $A$ and $B$ are free [see (a)], then amino acid 3 can be placed at position $A$ and 5 can be placed at position $B$. Then, to obtain a valid conformation, on the left side of amino acid 3, amino acid 2 is moved to the position of amino acid 3 and on the right side of amino acid 5, amino acid 6 is moved to the position of amino acid 5 [indicated in (b)].

Figure 6

Distribution of the standard errors of the lowest energies in all runs by the IELP and IWL methods for instances 1–12.

Figure 7

Conformations with the lowest energies found by the IWL method on the 2D fcc HP lattice model. Black and white circles indicate the hydrophobic and hydrophilic amino acids, respectively. Typical conformations are shown with (a) $E$ = −44 of instance 7, (b) $E$ = −71 of instance 8, (c) $E$ = −75 of instance 9, (d) $E$ = −101 of instance 10, (e) $E$ = −94 of instance 11, and (f) $E$ = −94 of instance 12.

Figure 8

Conformations with the lowest energies found by the IWL sampling method for six CASP target instances on the 3D fcc HP lattice model. The black and white balls indicate the hydrophobic and hydrophilic amino acids, respectively. Typical conformations are shown with (a) $E$ = −294 of instance $3mse$, (b) $E$ = −353 of instance $3mr7$, (c) $E$ = −443 of instance $3mqz$, (d) $E$ = −425 of instance $3no6$, (e) $E$ = −477 of instance $3no3$, and (f) $E$ = −561 of instance $3on7$.