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

Table 2. Comparison of results with the benchmark sequences

Seq. E min U&M GA [23] hybrid DE L&B DE [13] ACO [18]

S1 -9 -9 (30492) -9 ,-9 (3584, 6362) -9 ,-9 -9

S2 -9 -9 (30491) -9 ,-9 (5806, 9292) -9 ,-9 -9

S3 -8 -8 (20400) -8 ,-8 (7061, 18828) -8 ,-8 -8

S4 -14 -14 (301339) -14 ,-14 (45793, 92579) -14 ,-13.96 -14

S5 -23 -22 (126547) -23 ,-23 (245943, 532787) -23 ,-23 -23

S6 -21 -21 (592887) -21 ,-21(365222, 691989) -21 ,-21 -21

S7 -36 -34 (208781) -35,-33.57 -35,-34.79 -36

S8 -42 -37 (187393) -42 ,-42 (176313, 340917) -42 ,-41.87 -42

evaluations that obtained the best optimum value (second values after “,”). We
used 10 independent runs for each sequence.
There is not a clear rule about what the best number of individuals is, so,
for each sequence, we used population size = number of amino acids x 15 (as
suggested in [16] and [13]). One of the main factors to be compared is the number
of necessary evaluations to find the optimum. The work of Lopes and Bitello did
not include the number of evaluations to find their best values [13], so we only
included in the Table the best and average energy values reported by the authors.
The hybrid DE with the inclusion of the repair procedures reduces significantly
the number of conformations that are needed to scan in order to obtain the best
energy values, as it can be seen with such best minimum number of necessary
evaluations (first values in parentheses). Even the average values of the number
of necessary scanned conformations is lower with respect to the reported values
of Unger and Moult with a GA [23] (except for S6), taking into account that
their reported values are the best in 5 independent runs. Figure 4 shows three
examples of the best folded conformations obtained with the hybrid DE. For the
sequence S 7 the minimum was not obtained, although we allowed a maximum
number of 10 6 evaluations in the different runs.
In the case of Shmygelska and Hoos [18], using an ant colony optimization
(ACO), the authors obtained the best values in all the sequences. Their results
are dicult to compare with the evolutionary algorithms, as the authors used 500
runs of the ACO algorithm (in sequences S 1

S 6) and 100 runs for sequences
S 7and S 8, with a population of 100 ants and, additionally, half of the ants
performed a local search with a maximum of 1,000 scans through the protein
sequence ( S 1

−

S 6) or a maximum of 10,000 scans ( S 7and S 8). As the authors
commented, their empirical results indicated that their “rather simple ACO
algorithm scales worse with sequence length but usually finds that more diverse
ensemble of native states”.

−

5 Conclusions

We applied DE to the optimization of folded protein conformations using the
HP lattice model. DE provides a method with a reduced number of defining