An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets

Abstract

Background: Proteins are essential biological molecules which play vital roles in nearly all biological processes. It is the tertiary structure of a protein that determines its functions. Therefore the prediction of a protein's tertiary structure based on its primary amino acid sequence has long been the most important and challenging subject in biochemistry, molecular biology and biophysics. In the past, the HP lattice model was one of the ab initio methods that many researchers used to forecast the protein structure. Although these kinds of simplified methods could not achieve high resolution, they provided a macrocosm-optimized protein structure. The model has been employed to investigate general principles of protein folding, and plays an important role in the prediction of protein structures.

Methods: In this paper, we present an improved evolutionary algorithm for the protein folding problem. We study the problem on the 3D FCC lattice HP model which has been widely used in previous research. Our focus is to develop evolutionary algorithms (EA) which are robust, easy to implement and can handle various energy functions. We propose to combine three different local search methods, including lattice rotation for crossover, K-site move for mutation, and generalized pull move; these form our key components to improve previous EA-based approaches.

Results: We have carried out experiments over several data sets which were used in previous research. The results of the experiments show that our approach is able to find optimal conformations which were not found by previous EA-based approaches.

Conclusions: We have investigated the geometric properties of the 3D FCC lattice and developed several local search techniques to improve traditional EA-based approaches to the protein folding problem. It is known that EA-based approaches are robust and can handle arbitrary energy functions. Our results further show that by extensive development of local searches, EA can also be very effective for finding optimal conformations on the 3D FCC HP model. Furthermore, the local searches developed in this paper can be integrated with other approaches such as the Monte Carlo and Tabu searches to improve their performance.

Figure 1

A ground-state conformation in the 3D FCC HP model. An example on HP lattice model: (a) The native state of the protein with PDB id 1CNL, (b) an optimal HP conformation for 1CNL on 3D FCC lattice with 7 HH contacts denoted by dashed blue lines.

Figure 2

The FCC lattice model: each lattice point has 12 neighbours.

Figure 3

Main steps of the proposed EA-based approach.

Figure 4

Square-Based Rotation: 3 ways to partition the 12 neighbours of the central point into 3 squares.

Figure 5

Triangle-Hexagon-Based Rotations. Triangle-Hexagon-Based Rotations: 4 ways to partition the 12 neighbours of the central point into two triangles and one hexagon.

Figure 6

Rotation-based crossover operate. Illustration of rotation-based crossover: (a) and (b) are the parent conformations; (c) is the offspring without rotation; (d) shows the 3 squares in one partitioning of neighbours; (e) shows the corresponding label permutation for rotation angle 90°, 180° and 270°; (f) shows the 4 offspring with the part in red rotated 0°, 90°, 180° and 270°; (g), (i) and (j) illustrate triangle-hexagon-based rotation.

Figure 7

Generalized Pull Move. Generalized Pull Move on 3D FCC lattice: (a) shows the result obtained by the traditional Pull Move; (b) to (e) shows the 4 possible results obtained by Generalized Pull Move.

Figure 8

Configurations for F180_1, F180_2 and F180_3 obtained by our approach.

Figure 9

Configurations for sequences in Data Set IV obtained by our approach.