Differential Evolution for Protein Structure Prediction Using the HP Model - Foundations on Natural and Artificial Computation - page 328

encountered, it moves the amino acid that generates the conflict to the nearest
free position. In a second stage, the subsequent chain is reconstructed from the
new obtained positions, respecting the restrictions of the lattice model.
The second strategy works with the absolute moves (North, South, East and
West in the square lattice) to repair the chain conformation. Once a conflict
is found, it is changed the absolute move of the amino acid that generates the
conflict to obtain a position with no conflict. The procedure is repeated through
the rest of the protein conformation. Nevertheless, we did not use a complete
search as we did not perform backtracking strategies when there is not any free
position after checking all the possible moves. Figure 1 shows an example, where
Fig. 1.a is the illegal conformation, Fig. 1.b and Fig. 1.c are intermediate states
of this repair procedure and Fig. 1.d is the final feasible conformation. Figure 1.e
represents the final rectified conformation from the illegal one of Fig. 1.a using
the first procedure with the Cartesian coordinates.
The first strategy tries to obtain legal conformations searching for a similar
one in the Cartesian space, while the second tries to maintain the relative con-
formation of the rest of the chain which has not generated the conflict. In both
cases, when there is no possibility of a repair process, the illegal conformation
remains in the population (with fitness 0, so it will soon disappear).

Table 1. Benchmarks sequences, for the square lattice, used in the experiments

Length HP Chain E

20 HPHP 2 H 2 PHP 2 HPH 2 P 2 HPH S1 -9

H 2 P 2 HP 2 HP 2 HP 2 HP 2 HP 2 HP 2 H 2

S2 24 -9

P 2 HP 2 H 2 P 4 H 2 P 4 H 2 P 4 H 2 S3 25 -8

P 3 H 2 P 2 H 2 P 5 H 7 P 2 H 2 P 4 H 2 P 2 HP 2

S4 36 -14

P 2 HP 2 H 2 P 2 H 2 P 5 H 10 P 6 H 2 P 2 H 2 P 2 HP 2 H 5

S5 48 -23

H 2 PHPHPHPH 4 PHP 3 HP 3 HP 4 HP 3 HP 3 HPH 4 PHPHPHPH 2

S6 50 -21

P 2 H 3 PH 8 P 3 H 10 PHP 3 H 12 P 4 H 6 PH 2 PHP S7 60 -36

H 12 PHPHP 2 H 2 P 2 H 2 P 2 HP 2 H 2 P 2 H 2 P 2 HP 2 H 2 P 2 H 2 P 2 HPHPH 12 -42 S8 64

4R su s

We tested the DE implementation hybridized with the repair processes using
benchmark sequences employed in the literature. Table 1 shows these sequences
with different number of amino acids and the corresponding energy minima
(maximum number of HH contacts known up to now).
Regarding the DE implementation, we used standard values: CR =0 . 9and
F =0 . 9, whereas the size of the tournament to choose the base vector was 8% of
the population, which implies a low selective pressure when choosing such vector
to disturb.
Regarding the repair processes, as there is not a clear rule to determine what
the best strategy is, we used the two repair processes implemented. The first
one, which works with the Cartesian coordinates, is used beginning the conflict