Protein Folding Optimization using Differential Evolution
Extended with Local Search and Component Reinitialization

arXiv:1710.07031v1 [] 19 Oct 2017

Borko Bošković · Janez Brest

October 20, 2017

Abstract This paper presents a novel differential evolution algorithm for protein folding optimization that
is applied to a three-dimensional AB off-lattice model.
The proposed algorithm includes two new mechanisms.
A local search is used to improve convergence speed and
to reduce the runtime complexity of the energy calculation. For this purpose, a local movement is introduced
within the local search. The designed evolutionary algorithm has fast convergence and, therefore, when it
is trapped into local optimum or a relatively good solution is located, it is hard to locate a better similar
solution. The similar solution is different from the good
solution in only a few components. A component reinitialization method is designed to mitigate this problem.
Both the new mechanisms and the proposed algorithm
were analyzed on well-known amino-acid sequences that
are used frequently in the literature. Experimental results show that the employed new mechanisms improve
the efficiency of our algorithm and the proposed algorithm is superior to other state-of-the-art algorithms.
It obtained a hit ratio of 100 % for sequences up to 18
monomers within a budget of 1011 solution evaluations.
New best-known solutions were obtained for most of the
sequences. The existence of the symmetric best-known
solutions is also demonstrated in the paper.
Keywords Protein folding optimization · Threedimensional AB off-lattice model · Differential
evolution · Local search · Component reinitialization
B. Bošković
Faculty of Electrical Engineering and Computer Science,
University of Maribor, SI-2000 Maribor, Slovenia
E-mail: borko.boskovic@um.si
J. Brest
Faculty of Electrical Engineering and Computer Science,
University of Maribor, SI-2000 Maribor, Slovenia
E-mail: janez.brest@um.si

1 Introduction
The protein structure prediction represents the problem of how to predict the native structure of a protein from its amino-acid sequence. This problem is one
of the more important challenges of this century [17]
and, because of its nature, it attracts scientists from
different fields, such as Physics, Chemistry, Biology,
Mathematics, and Computer Science. Within the protein structure prediction, the Protein Folding Optimization (PFO) represents a computational problem for simulating the protein folding process and to find a native
structure. Most proteins must fold into unique threedimensional structure, known as a native structure, to
perform their biological function [2]. Protein function
is determined by its structure. Inability of a protein to
form its native structure prevents a protein from fulfilling its function correctly, and this may be the basis of
various human diseases [1, 25, 28, 29].
The PFO belongs to the class of NP-hard problems [11] and, with current algorithms and computational resources, it is possible to predict the native structures of relatively small proteins. The reason for that is
the huge and multimodal search space. For example, a
polypeptide that has only 18 amino-acids, will have 31
angles within a simplified AB model (see Section 3). Using uniform discretization with only 10 values for each
angle, there would be 1031 possible configurations. To
evaluate and select the correctly folded conformation
among all these conformations in the time elapsed since
the Big Bang, we need the huge computational speed
of 1031 /(4.32 · 1017 ) = 2.31 · 1013 conformation evaluations per second. This is much faster than the speed
obtained within our experiment, where we can evaluate
only 5.73 · 105 conformations per second. From these
numbers, we can see that the search space is huge, even

2

in the simplified model, which makes this problem very
hard. However, in reality, the proteins fold into their
native conformation on a time scale of seconds, and
this contradiction is known as Levinthal’s paradox [7].
An optimization algorithm can give good results of a
PFO problem only if it can locate good solutions and
evaluate solutions efficiency. Here, the approximation
techniques, such as heuristic and metaheuristic, with
efficient data structures, become the only viable alternatives as the problem size increases.
There exist some simplified protein models, such
as HP models within different lattices [5, 21] and the
AB off-lattice model [30, 31]. Simplified protein models
were designed for development, testing, and comparison
of different approaches. The AB off-lattice model was
used in the paper for demonstrating the efficiency of
the proposed algorithm. This model takes into account
the hydrophobic interactions which represent the main
driving forces of a protein structure formation and, as
such, still imitates its main features realistically [14].
Although this model is incomplete, it allows the development, testing, and comparison of various search
algorithms, and offers a global perspective of protein
structures. It can be helpful in confirming or questioning important theories [3].
In our recent work [4], we proposed a Differential
Evolution (DE) [32,33] algorithm for PFO that includes
DE /best/1 /bin strategy, self-adaptive mechanism [6] of
main control parameters, random reinitialization and
temporal locality mechanism [10, 38]. This algorithm
belongs to the ab-initio PFO methods, which optimize
structures from scratch and do not require any information about related sequences. It showed a very fast convergence, and it was capable of obtaining significantly
better results than other state-of-the-art algorithms.
In this paper, we propose two new mechanisms, that
additionally, improve the efficiency of our algorithm. A
new local search mechanism was designed in order to
improve convergence speed and to reduce runtime complexity of the algorithm. A similar idea was already used
within the HP model [5], where it is applied to the cubic
lattice. Using a simple local search mechanism where
only one solution’s component is changed can produce
a structure whereby a lot of monomers are moved. This
means their positions must be recalculated and efficient energy calculation is not possible. In contrast to
simple local search, our mechanism improves the quality of conformations using the local movements within
the three-dimensional AB off-lattice model. We define
a local movement as a transformation of conformation
whereby only two consecutive monomers are moved locally in such a way that the remaining monomers remain in their positions. In such a way, the designed

Borko Bošković, Janez Brest

local movement allows efficient evaluation of neighborhood solutions. With the fast convergence, the algorithm can locate good solutions quickly, but it has a
problem locating good similar solutions. For that purpose, a component reinitialization was designed and incorporated within our algorithm. This mechanism is
employed when the local best solution is detected. It
produces similar solutions that are different from the
local best solution in only a few components.
We called the proposed algorithm DElscr and it was
tested on two sets of amino-acid sequences that were
used frequently in the literature. The first set included
18 real peptide sequences, and the second set included
4 well-known artificial Fibonacci sequences with different lengths. Experimental results show that the proposed mechanisms improve the efficiency of the algorithm, and the algorithm is superior to other stateof-the-art algorithms. Its superiority is especially evident for larger sequences. With the proposed algorithm,
that is stochastic, we cannot prove optimality of the
obtained conformations. However, we can infer about
them according to the observed hit ratio. The experimental results show that our algorithm obtained hit
a ratio of 100 % for sequences that contain up to 18
monomers. For all larger sequences, we can only report
the best-known conformations that are almost surely
not optimal. Based on these observations, the main contributions of this paper are:
1. The proposed new DE algorithm for the PFO on a
three-dimensional AB off-lattice model.
2. The local search mechanism that improves convergence speed and reduces runtime complexity of solution evaluations within the neighborhood.
3. The component reinitialization which increases the
likelihood of finding good similar solution.
4. With the observed hit ratios we show how difficult
the PFO is, even in a simplified model, and that,
with the current algorithm, we can confirm solutions
with a hit ratio of 100 % only for sequences that have
up to 18 monomers.
5. An approach for determining the algorithm’s asymptotic average-case performances.
6. The existence of two best-known (potentially global
best) structures that are symmetrical for all sequences
with up to 25 monomers.
7. The new best-known conformations for most of the
sequences.
The remainder of this paper is organized as follows.
A related work for the PFO on a three-dimensional AB
off-lattice model is described in Section 2. The threedimensional AB off-lattice model is described in Section 3. A description of the introduced algorithm with
the emphasis on new mechanisms is given in Section 4.

Protein Folding Optimization using DE with Local Search and Component Reinitialization

The experimental setup and numerical results are presented in Section 5. Section 6 concludes this paper.
2 Related work
Over the years, different algorithms have been applied
successfully to the PFO on a three-dimensional AB offlattice model. In [12] the low energy configurations are
optimized using the pruned-enriched-Rosenbluth method (PERM). This method was applied to the lattice
model quite successfully [34]. The conformational space
annealing was studied using Fibonacci sequences in [20]
and compared with nPERMis (new PERM with importance sampling) [13]. Next, the algorithm that was compared with the nPERM algorithm was proposed in [8].
In this work, the problem is converted from a nonlinear constraint-satisfied problem to an unconstrained optimization problem which can be solved by the wellknown gradient method. The statistical temperature
molecular dynamics based algorithm ”statistical temperature annealing” was applied to an AB model in [18].
The efficiency of an improved tabu search algorithm
was analyzed in [39]. The following hybrid algorithms
were also developed for the AB model: A hybrid algorithm that combines the genetic algorithm and tabu
search algorithm [35, 36, 40], particle swarm optimization and levy flight [9], the particle swarm optimization,
genetic algorithm, and tabu search algorithm [41], and
improved genetic algorithm and particle swarm optimization algorithm with multiple populations [42]. An
artificial bee colony algorithm [22–24, 37] and an improved harmony search algorithm that is combined with
dimensional mean based perturbation strategy [15] were
also analyzed on the AB model.
The authors in [16] determined the structural features of the PFO using Fitness Landscape Analysis
(FLA) techniques based on the generated landscape
path. From the results of FLA, it has been shown that
the PFO has a highly rugged landscape structure containing many local optima and needle-like funnels, with
no global structure that characterizes the PFO complexity. The obtained results also show that the artificial bee colony algorithm outperforms all other algorithms significantly in all instances for the three-dimensional AB off-lattice model.
In our recent work [4], we proposed a differential
evolution algorithm that is adapted to PFO on a threedimensional AB off-lattice model. Within this algorithm,
we incorporated a self-adaptive mechanism, a mutation
strategy for the fast convergence and a temporal locality. The obtained results of this algorithm show that it
is superior to the algorithms from the literature, including the artificial bee colony algorithm, and significantly

3

lower free energy values were obtained for longer AB
sequences.

3 Three-dimensional AB off-lattice model
The basic building blocks of proteins are amino-acids.
The linear chain of amino acids is a polypeptide, and
a protein contains at least one long polypeptide. Each
polypeptide can be represented with a unique amino
acid sequence. The polypeptide must fold into a specific three-dimensional native structure before it can
perform its biological function(s) [27]. Thus, all information necessary for folding must be contained in the
amino-acid sequence, and this is known as the Anfinsenhypothesis [7].
From the amino-acid sequence it is possible to generate different conformations, which is also dependent
on the used model. In general, there exist two types
of simplified models: Off-lattice and lattice. The lattice
model maps each position of amino-acid to the point
on a discrete lattice. In contrast to the lattice model,
the off-lattice model allows any position and, as such,
is more accurate. The simplified three-dimensional AB
off-lattice model was proposed in [31]. Instead of 20
standard amino-acids, this model uses only two different types of amino-acids: A – hydrophobic and B – hydrophilic. Thus, an amino-acid sequence is represented
as a string s = {s1 , s2 , ..., sL }, si ∈ {A, B}, where A
represents a hydrophobic, B a hydrophilic amino-acid
and L the length of the sequence. The three-dimensional
structure of an AB sequence is defined by bond angles
θ = {θ1 , θ2 , ..., θL−2 }, torsional angles β = {β1 , β2 , ...,
βL−3 } and the unit-length chemical bond between two
consecutive amino-acids (see Fig. 1).
Different energy calculations can be used within different models. Within an AB model, the free energy
value is calculated using a simple trigonometric form of
backbone bend potentials E1 (θ) and a species-dependent
Lennard-Jones 12,6 form of non-bonded interactions
E2 (s, θ, β) as shown in the following equation [31]:
E(s, θ, β) = E1 (θ) + E2 (s, θ, β)
E1 (θ) =

L−2
1 X
[1 − cos(θi )]
4 i=1

E2 (s, θ, β) = 4

L−2
X

L
X

(1)

[d(pi , pj )–12 –c(si , sj ) · d(pi , pj )–6 ]

i=1 j=i+2

where pi = {xi , yi , zi } represents the position of the i-th
amino-acid within the three-dimensional space. These
positions are determined as shown in Fig. 1 and by the
following equation:

4

Borko Bošković, Janez Brest

(a)

(b)

Fig. 1 A schematic diagram of a sequence ABAB. (a) Projection of a structure with θ1 = 30, θ2 = −60 and β1 = 0 onto the
XY-plane. (b) Projection of a structure with θ1 = 30, θ2 = −60 and β1 = 45 onto the ZY-plane.

4.1 Proposed algorithm


{0, 0, 0}





{0, 1, 0}



{cos(θ ), 1 + sin(θ ), 0}
1
1
pi =

{xi−1 + cos(θi−2 ) · cos(βi−3 ),





yi−1 + sin(θi−2 ) · cos(βi−3 ),



 z
i−1 + sin(βi−3 )}

if i = 1,
if i = 2,
if i = 3,

(2)

if 4 ≤ i ≤ L.

In Eq. (1) d(pi , pj ) denotes the Euclidean distance between positions pi and pj , while c(si , sj ) determines
the attractive, weak attractive or weak repulsive nonbonded interaction for the pair si and sj as shown in
the following equation:


1
c(si , sj ) = 0.5


−0.5

if si = A and sj = A,
if si = B and sj = B,
if si 6= sj .

The objective of PFO within the context of an AB offlattice model is to simulate the folding process and to
find the angles’ vector or conformation that minimizes
the free-energy value:
{θ ∗ , β ∗ } = arg min E(s, θ, β).

4 Proposed algorithm for PFO
In this paper, we extend our differential evolution algorithm [4] with two new mechanisms. The first mechanism is a local search that improves convergence speed
and reduces runtime complexity for solution evaluation
within the specific neighborhood. The second mechanism is component reinitialization, which allows the algorithm to locate good similar conformations according
to the local best solution.

Hereinafter, we will describe briefly the DElscr algorithm that is shown in Fig. 2. The lines that represent improvements according to the previous version
are highlighted with gray background. The optimization process begins with initialization (line 2). Each iteration of while loop (line 3) represents one generation
of the evolutionary process. A mutation, crossover, and
selection are performed for each population’s individual
{x1 , x2 , ..., xNp } within one generation. The DE /best/1
mutation strategy and binary crossover (lines 7 – 18)
are used for creating a trial individual u. The values
of mutation F , and crossover Cr control parameters
are set with the self-adaptive jDE mechanism (lines 5
and 6) [6]. The trial individual is evaluated in line 19
using Eq. (1). From this line, we can see that the individuals are D-dimensional vectors that contain real
coded bond θ and torsional β angles:
xi = {xi,1 , xi,2 , ..., xi,D } =
= {θ1 , θ2 , ..., θL−2 , β1 , β2 , ..., βL−3 }
xi,j ∈ [−π, π];

D =2·L−5

i = 1, 2, ..., Np;

j = 1, 2, ..., D

The selection mechanism, temporal locality and local
search are shown in lines 20 – 40. If the trial vector
is better than the corresponding vector from the population (eu < ei ), then the second trial vector u∗ is
generated using temporal locality [38] and the better
vector replaces population vector xi . The next mechanism is a local search. Within this mechanism, a local
movement is used for improving the population best
individual xpb according to each pair {θn−1 , βn−2 }. The
values of {θn−1 , βn−2 } represent the angles that specify
the position of the (n + 1)-th monomer according to
the position of the n-th monomer. After each generation, either random or component reinitialization will

Protein Folding Optimization using DE with Local Search and Component Reinitialization
1: procedure DElscr (s, Np)
2:
Initialize a population P
{xi , Fi = 0.5, Cr i = 0.9, ei = E(s,xi )} ∈ P
xi,j = −π + 2 · π · rand [0,1]
i = 1, 2, ..., Np; j = 1, 2, ..., D; D = 2 · length(s) − 5

7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

p
{xb , eb } = {xlb , elb } = {xp
b , eb } = BEST(P )
while stopping criteria is not met do
for i = 1 to Np do
if rand [0,1] < 0.1 then F = 0.1 + 0.9 · rand [0,1]
else F = Fi end if
if rand [0,1] < 0.1 then Cr = rand [0,1]
else Cr = Cr i end if
do r1 =rand {1,Np} while r1 =i end do
do r2 =rand {1,Np} while r2 =i or r2 =r1 end do
jrand = rand {1,D}
for j = 1 to D do
if rand [0,1] < Cr or j = jrand then
uj = xb,j + F · (xr1 ,j − xr2 ,j )
if uj ≤ -π then uj = 2 · π + uj end if
if uj > π then uj = 2 · (-π) + uj end if
else
uj = xi,j
end if
end for
eu = E(s,u) // Energy calculation
if eu ≤ ei then
// Temporal locality
for j = 1 to D do
u∗
j = xb,j + 0.5 · (uj − xi,j )
∗
∗
if u∗
j ≤ -π then uj = 2 · π + uj end if
∗
if u∗
>
π
then
u
=
2
·
(-π)
+
u∗
j
j
j end if
end for
∗
e∗
u = E(s,u )
if e∗
u ≤ eu then
{xi , Fi , Cri , ei } = {u∗ , F, Cr , e∗
u}
else
{xi , Fi , Cri , ei } = {u, F, Cr , eu }
end if
// Local Search

34:
35:

for n = 2 to L − 1 do
θn-1 = rand [0,1] · (xp
b,n-1 − xi,n-1 )

3:
4:
5:
6:

36:

βn-2 = rand [0,1] · (xp
b,n+(L-4) − xi,n+(L-4) )

37:

{v, ev } = LOCAL MOVEMENT(xp
b , n, θn-1 , βn-2 )

38:
39:
40:
41:
42:

p
if ev ≤ eb then {xp
b , ei } = {v, ev } end if
end for
end if
end for
p
{xp
b , eb } = BEST(P )

43:

p p
if ep
b ≤ eb then {xb , eb } = {xb , eb } end if

p
l
l
REINITIALIZATION({xp
44:
b , eb },{xb , eb },P )
45:
end while
46:
return {xb , eb }
47: end procedure

Fig. 2 The proposed DElscr algorithm.

be performed if the reinitialization criteria are satisfied
(line 44). At the end of the evolutionary process, the
algorithm returns the best obtained solution xb and its
energy value eb , as shown in line 46. The local search

5

and reinitialization are described in more detail in the
following subsections. For a detailed description of the
rest mechanism, we refer readers to [4].

4.2 Local search
If the trial vector is better than the corresponding population vector, then the temporal locality and local search
are performed. The local search calculates the values of
pair {θn−1 , βn−2 } for each monomer, with the exception of the first two monomers. Positions of these two
monomers are fixed within the AB-model, see Eq. (2).
For the rest monomers, the angle values are defined
with a randomly scaled difference between the population best individual xb and current individual xi , as
shown in the following equation:
θn−1 = rand [0,1] · (xpb,n−1 − xi,n−1 )
βn−2 = rand [0,1] · (xpb,n+(L−4) − xi,n+(L−4) )
i = 1, ..., Np;

n = 2, ..., L − 1;

A meticulous reader may notice that the θ has index
n − 1, while β has index n − 2. This means that, for
n = 2 the value of β0 is calculated using the values of
θ components. The reason for that is in the position of
the third monomer, which is dependent only on the θ1 ,
see Eq. (2). Therefore, within the local movement for
n = 2 the value of β0 is ignored, and local movement
takes into account only the value of θ1 .
The local movement is a transformation of conformation whereby only two consecutive monomers are
moved locally in such a way that the remaining monomers remain in their positions. There is only one exception, for the last monomer only one monomer is moved,
while all the remaining monomers remain in their positions. Fig. 3 shows an example of two monomers’ local
movement. The polygon that is defined with points P1 ,
P2 , P3 , P4 represents the section of original conformation where points represent the monomer positions. The
local movement moves the point P2 to the point X2 according to the pair {θn−1 , βn−2 } while the position of
point X3 is calculated using Eqs. (3) – (6). In these
calculations, the point X3 is the nearest to the point
P3 in such a way that the new polygon P1 , X2 , X3 ,
P4 must end at the point P4 .
The calculation begins with the determination of
point C whose position is in the middle of points P4
and X2 :
C = X2 +

P4 − X2
.
2

(3)

The length L between points C and X3 is calculated by
using the triangle P4 , C, X3 and Pythagoras’s theorem:

6

Borko Bošković, Janez Brest

Fig. 3 A schematic diagram of a local movement. The polygon P1 , P2 , P3 , P4 is transformed to polygon P1 , X2 , X3 , P4
in such a way that only the two consecutive points P2 and P3 are moved to points X2 and X3 , while the remaining points
P1 and P4 stay unchanged in their positions.

∆e2 =

s
L=

2

1−

kP4 − X2 k
.
4

P4 − X2
.
kP4 − X2 k

(4)

(P3 − C) − CN
· L.
k(P3 − C) − CN k

(5)

(6)

The created polygon contains unchanged points P1 and
P4 , which means only monomers X2 and X3 are moved
locally, while the remaining monomers stay in their
unchanged positions. This feature allows us to design
the fast conformation evaluation within the local movement. Two additional data structures E1 and E2 were
used for this purpose. The values of elements within
these data structures are determined according to Eq.
(1), as follows:
E1i = 1 − cos(θi )
E2i,j = d(pi , pj )−12 − c(si , sj ) · d(pi , pj )−6
i ∈ {1, ..., L − 2};

j ∈ {i + 2, ..., L}.

Using these data structures for the population best individual and its energy value, we can calculate the energy of the conformation created by local movement
efficiently, as is shown in Eqs. (7) – (9) where n represents the variable that was sent to the local movement
procedure, as shown in Fig. 2 (see line 37).
∆e1 = E1n−1 − (1 − cos(θn−1 )) +
E1n − (1 − cos(θn )) +
E1n+1 − (1 − cos(θn+1 ))

E2i,j −

d(pi , pj )−12 − c(si , sj ) · d(pi , pj )−6
n+3
X

i h
X

i

E2j,i −

+
(8)

i=n+1 j=1

At the end, point X3 is calculated by scaling of vector
(P3 − C) − CN as follows:
X3 = C +

L
h
X

i=n+1 j=n+2

The vector projection of (P3 − C) onto line X2 , P4 is
calculated with the following equation:
CN = (P3 − C) ·

n+3
X

(7)

d(pi , pj )−12 − c(si , sj ) · d(pi , pj )−6

i

∆e1
+ 4 · ∆e2 )
(9)
4
From Eqs. (7) – (9) we can observe that the time com2
plexity of energy calculation is reduced from L2 to 2L.
In this way, the designed local movement allows faster
evaluation of neighborhood solutions, and its usage within local search improves convergence speed.

ev = epb − (

4.3 Reinitialization
After each generation reinitialization will be performed
if the reinitialization criteria are satisfied. In our previous work, random reinitialization will be performed
if the best individual stays unchanged within the evolution process for more than 105 evaluations. In this
work we design a new reinitialization mechanism. For
that purpose, the algorithm includes three types of best
individuals and three new control parameters, as shown
in Fig. 4. The individuals xpb , xlb , xb represent the population best, local best and global best individuals. The
population best individual is the best individual in the
current population, the local best individual is the best
individual among all similar individuals, and the global
best individual is the best individual obtained within
the evolutionary process. From this description of the
best individuals, we can see that reinitialization has to
control evolutionary process to:

Protein Folding Optimization using DE with Local Search and Component Reinitialization
p
l
l
1: procedure REINITIALIZATION({xp
b , eb },{xb , eb },P )
is
unchanged
for
at
least
P
·
D
evaluations
then
2:
if xp
b
b
p p
l
l
l
3:
if ep
b ≤ eb then {xb , eb } = {xb , eb } end if
4:
if xlb is unchanged for Lb · D reinitializations then
5:
// Random reinitialization
6:
xi = RANDOM() ; i = 1, 2, ..., Np
p
7:
{xlb , elb } = {xp
b , eb } = BEST(P )
8:
else
9:
// Component reinitialization
10:
xi = RANDOM(xlb , C); i = 1, 2, ..., Np
p
11:
{xp
b , eb } = BEST(P )
12:
end if
13:
end if
14: end procedure

Fig. 4 The reinitialization mechanism.

• Locate the best individual by using the current population,
• Locate the best similar individual by using component reinitialization, and
• Locate the global best individual by using random
reinitialization.
The following new control parameters are introduced
to the reinitialization mechanism: Pb , Lb and C. The
Pb defines how long the best population individual can
stay unchanged within the evolutionary process (line 2).
For example, with Pb = 100 and dimension 21, the
reinitialization is required if the best population individual stayed in the evolutionary process for at least
Pb · D = 100 · 21 = 2100 evaluations. When this condition is satisfied, the algorithm performs random or component reinitialization according to the parameter Lb . If
the local best individual is not changed for Lb · D reinitializations, then random reinitialization is performed,
and component reinitialization otherwise (line 4). The
last parameter C determines the number of components that are different between the local best individual and individuals generated by component reinitialization (line 10). Within this operation, the C components of each population individual xi are selected, and
their values are replaced with random values on the interval [−π, π], while all the remaining components get
the values from the local best individual.

5 Experiments
The DElscr algorithm was compiled with a GNU C++
compiler 4.6.3 and executed using an Intel Core i7 computer with 2.93 GHz CPU and 8 GB RAM under Linux
Mint 13 Maya and a grid environment (Slovenian Initiative for National Grid1 ). In order to evaluate the
efficiency of the proposed algorithm, we used a set of
1

Available at http://www.sling.si/sling/

7

amino-acid sequences as shown in Table 1. This set includes 5 Fibonacci sequences and 18 real peptide sequences from the Protein Data Bank database2 . The
K-D method is used to transform real peptide sequences
to the AB sequences. In this method the amino acids I,
V, P, L, C, M, A, and G are transformed to hydrophobic ones (A) and amino acids D, E, H, F, K, N, Q, R,
S, T, W, and Y to hydrophilic ones (B) [26]. The selected sequences have different lengths, which enabled
us to analyze the algorithm according to different problem dimensions and, because they were used frequently
in literature, they enabled us to compare the proposed
algorithm with different algorithms. In order to analyze the efficiency of the introduced mechanisms and
algorithm, we measured the following statistics:
• The mean obtained energy value for all runs:
PN

i=1

Emean =

Ei

N

where Ei denotes the obtained energy value for the
i-th run and N the number of all runs.
• The best obtained energy value among all runs:
Ebest = max{E1 , E2 , ..., EN }.
Note that all energy values within our experiments
are multiplied by -1, which means that all energy
values are positive and higher values are better.
• The standard deviation of energy values for all runs:
s

PN

− Emean )2
N −1

i=1 (Ei

Estd =

• The hit ratio or percentage of runs during which
the best solution has equal or better energy value
according to the target value (target):
hitr =

Nh
N

where Nh denotes the number of runs where the best
obtained solution has good enough energy value eb
according to the target value (eb ≥ target).
• The mean number of solution evaluation for all Nh
runs:
PNh
NSE i
NSE mean = i=1
Nh
where NSE i represents the number of solution evaluations for the i-th run.
2

Available at https://www.rcsb.org/pdb/home/home.do

8

Borko Bošković, Janez Brest

Table 1 Details of amino-acid sequences used in experiments.
Label
1BXP
1CB3
1BXL
1EDP
2ZNF
1EDN
2H3S
1ARE
2KGU
1TZ4
1TZ5
1AGT
1CRN
2KAP
1HVV

Length
13
13
16
17
18
21
25
29
34
37
37
38
46
60
75

D
21
21
27
29
31
37
45
53
63
69
69
71
87
115
145

1GK4

84

163

1PCH

88

171

2EWH

98

191

F13
F21
F34
F55
F89

13
21
34
55
89

21
37
63
105
173

Sequence
ABBBBBBABBBAB
BABBBAABBAAAB
ABAABBAAAAABBABB
ABABBAABBBAABBABA
ABABBAABBABAABBABA
ABABBAABBBAABBABABAAB
AABBAABBBBBABBBABAABBBBBB
BBBAABAABBABABBBAABBBBBBBBBBB
ABAABBAABABBABAABAABABABABABAAABBB
BABBABBAABBAAABBAABBAABABBBABAABBBBBB
AAABAABAABBABABBAABBBBAABBBABAABBABBB
AAAABABABABABAABAABBAAABBABAABBBABABAB
BBAAABAAABBBBBAABAAABABAAAABBBAAAAAAAABAAABBAB
BBAABBABABABABBABABBBBABAABABAABBBBBBABBBAABAAABBABBABBAAAAB
BAABBABBBBBBAABABBBABBABBABABAAAAABBBABAABBABBBABBAABBABBAABBBB
BAABBBBBABBB
ABABAABABBBBABBBABBABBBBAABAABBBBBAABABBBABBABBBAABBABBBBBAABAB
AAABABAABBBBAABABBBBA
ABBBAAABBBAAABABAABAAABBABBBBBABAAABBBBABABBAABAAAAAABBABBABABA
BABBABBAABAABBBAABBAAABA
AABABAAAAAAABBBAAAAAABAABAABBAABABAAABBBAAAABABAAABABBAAABAAABA
AABAABBAABAAAAABAAABABBBABBAAABAABA
ABBABBABABBAB
BABABBABABBABBABABBAB
ABBABBABABBABBABABBABABBABBABABBAB
BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB
ABBABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBABABBABBAB
ABBABBABABBABABBABBABABBAB

• The standard deviation of solution evaluations for
all Nh runs:
s
PNh
2
i=1 (NSE i − NSE mean )
NSE std =
Nh − 1
• The mean runtime for all runs:
PN
ti
tmean = i=1
N
where ti represents the runtime of the i-th run.
• The mean speed for all runs:
PN
vi
vmean = i=1
N
where vi represents the speed (the number of solution evaluations per second) of the i-th run.
The listed statistics were measured within the context
of the following stopping conditions:
• The maximum number of solution evaluations
NSElmt : NSE i ≥ NSE lmt .
• The runtime limit tlmt : ti ≥ tlmt .
• The energy value of the best obtained solution target:
eb ≥ target.
Our algorithm belongs to stochastic algorithms, therefore, all the reported results of the proposed algorithm
within this work are based on N = 100 independent
runs. The described statistics, the defined stopping criteria and the determined number of independent runs
were used to analyze the influence of new parameters

and mechanisms on the algorithm’s efficiency. The algorithm was also compared with the state-of-the art
algorithms. The asymptotic average-case performances
were determined for the 6 shortest sequences and an
analysis of the obtained conformations was also performed and will be given in the continuation of the paper.

5.1 Parameter settings
The influence of the new control parameters (Pb , Lb , C)
on the algorithm’s efficiency was analyzed by using Fibonacci sequences. In this analysis, the stopping condition was the maximum number of solution evaluations
NSElmt = 1010 . For each sequence, we started with the
following setting: Pb = 50, Lb = 10, and C = 5. Using 6 settings, where only one value of each setting was
changed to the nearest higher or lower value, we tried
to get better settings. The parameter values are used
from the following sets:
Pb ∈ {10, 25, 50, 100}
Lb ∈ {1, 2, 5, 10, 20, 50}
C ∈ {2, 5, 10, 20}
For the started setting the following 6 settings were
used:
{ Pb = 10, Lb = 10, C = 5}, {Pb = 25, Lb = 10, C = 5},
{ Pb = 50, Lb = 5, C = 5}, {Pb = 50, Lb = 20, C = 5},
{ Pb = 50, Lb = 10, C = 2}, {Pb = 50, Lb = 10, C = 10}.

Protein Folding Optimization using DE with Local Search and Component Reinitialization

9

Table 2 The analysis of the new control parameters (Pb , Lb , C). N = 100 independent runs were performed for each setting
and the stopping conditions were the maximum number of solution evaluations NSElmt = 1010 and target value.
Pb Lb C
50 2 5
100 2 5
25 2 5
50 5 5
50 2 10
50 1 5
50 10 5
50 2 2

Emean
6.9961
6.9961
6.9961
6.9961
6.9961
6.9961
6.9961
6.9847

Estd
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.03

hitr
NSE mean
NSE std
100 6.41E+07 5.59E+07
100 6.88E+07 5.96E+07
100 7.52E+07 7.01E+07
100 9.07E+07 8.06E+07
100 9.52E+07 9.67E+07
100 9.59E+07 9.55E+07
100 9.77E+07 9.48E+07
90 3.15E+09 2.67E+09

Pb
25
25
50
50
10
25
25
25

Lb C
20 5
10 5
10 5
20 5
20 5
50 5
20 10
20 2

Emean
16.4500
16.4492
16.4432
16.4415
16.4307
16.4254
16.4037
15.4393

(a) F13, target = 6.9961
Pb
50
50
25
50
100
50
50

Lb
10
20
10
5
10
10
10

C
5
5
5
5
5
10
2

Emean
30.0670
30.0596
30.0519
29.9108
29.9034
29.3722
24.2650

(c) F34

Estd
0.45
0.40
0.47
0.38
0.47
0.35
1.94

Estd hitr
NSE mean
NSE std
0.09 21 4.91E+09 2.75E+09
0.08 19 4.89E+09 2.81E+09
0.08 17 3.92E+09 2.98E+09
0.10 22 4.86E+09 3.17E+09
0.09 15 3.93E+09 2.51E+09
0.12 33 4.84E+09 2.85E+09
0.08
2 7.94E+09 2.53E+09
0.45
0
-

(b) F21, target = 16.5544
Pb
25
25
10
50
25
25
25

Lb
5
10
5
5
2
5
5

C
10
10
10
10
10
5
20

Emean
49.0262
49.0233
49.0148
48.9379
48.9192
47.8458
47.4250

Estd
0.78
1.26
1.05
1.19
1.03
1.74
0.88

(d) F55

We repeated this process until the new better setting
was found. The results of the least iterations, together
with recommended settings, are shown in Table 2. For
clarity, the recommended settings and their results are
shown in bold typeface. The displayed results show that
each sequence has its own optimal setting, but it is still
possible to select settings that can be used for any unknown sequence. We define these settings according to
the dimension of the problem, as follows:
(
{50, 10, 5} if n < 45
{Pb , Lb , C} =
{25, 5, 10} otherwise.
These settings are used in all the following experiments,
because they can provide a good hit ratio for small sequences and good energy values for larger sequences.
The search space for larger sequences is huge, which
means the algorithm cannot provide optimal or suboptimal solutions. Therefore, for these sequences, the algorithm has to perform more reinitializations, and the
component reinitialization has to change more components randomly.
The shown results confirm, additionally, that the
variable NSE have near-exponential or near-geometric
distribution (NSE mean ≈ NSE std ). Under such distributions, given the Nh = 100 runs in all of our experiments, a reliable rule-of-thumb estimates the 95% confidence interval:
1.96
1.96
CI 95 ≈ [(1 − √ ) · NSE mean , (1 + √ ) · NSE mean ]
Nh
Nh
≈ [0.8 · NSE mean , 1.2 · NSE mean ].

Pb
50
25
50
25
50
100
50
50

Lb
2
2
5
5
1
2
2
2

C
10
10
10
10
10
10
5
20

Emean
76.8608
76.6879
76.5090
76.4541
76.3478
76.3275
75.1975
75.0143

Estd
1.64
1.89
1.88
1.93
1.40
1.71
2.62
1.52

(e) F89

5.2 Local search
The local search within our algorithm was designed to
increase the speed of algorithm convergence and speed
of neighborhood solution evaluations. In order to demonstrate these advantages, the algorithm was analyzed
with (DElscr ) and without (DEwls
lscr ) local search. Within
this analysis, the algorithms were compared using the
following stopping conditions: NSE lmt = 107 and tlmt =
tmean (DEwls
lscr ), as shown in Table 3. With the first stopping condition, we show that the local search improves
mean energy value Emean on 16 out of 23 sequences
and reduces the mean runtime tmean for all sequences.
Using the second stopping condition, both algorithms
were limited with the same runtime and, in this case,
local search improves Emean in 22 out of 23 sequences.
These values are marked in bold typeface within the
table. Results also show that speed up factor cv was
1.46 for the smallest sequences (F13 and 1BXP) and
3.91 for the largest sequence 2EWH, while the Emean
is worse by 0.0171 for sequence 1CB3 and better for
all other sequences. For the largest sequence 2EWH,
the improvement of Emean was huge, from 182.2880 to
205.3507 or by 23.0627.
From the obtained results, we can conclude that the
local search improves the convergence speed of the algorithm for most of the sequences, while the speed of solution evaluation is increased for all sequences. Somebody
would expect better speed up factor, but note that some
conditions must be satisfied for local search and, there-

10

Borko Bošković, Janez Brest

Table 3 The influence of the local search to the algorithm’s efficiency according to two algorithms: DElscr - with local
search and DEwls
lscr - without local search. Two different comparisons were made according to two different stopping conditions:
NSE lmt = 107 and tlmt = tmean (DEwls
lscr ). The reported mean speed vmean represents the mean number of function evaluations
per second, cv represents the speed up factor vmean (DElscr )/vmean (DEwls
lscr ) and the mean runtime tmean is given in seconds.
NSE lmt = 107
Label
1BXP
1CB3
1BXL
1EDP
2ZNF
1EDN
2H3S
1ARE
2KGU
1TZ4
1TZ5
1AGT
1CRN
2KAP
1HVV
1GK4
1PCH
2EWH
F13
F21
F34
F55
F89

DEwls
lscr

DElscr
tmean
12.54
12.18
15.02
16.00
17.44
20.27
24.85
29.37
34.89
37.47
36.66
38.81
51.66
76.79
104.64
122.54
130.19
162.03
12.42
20.90
35.89
71.27
140.58

vmean
Emean
Estd
7.98E+05
4.7280 0.24
8.22E+05
7.9643 1.02
6.67E+05 16.2149 0.51
6.25E+05 13.7281 1.07
5.74E+05 16.1670 1.86
4.94E+05 17.9565 2.51
4.03E+05 15.1685 2.36
3.41E+05 19.3024 1.92
2.87E+05 43.6622 3.46
2.68E+05 28.7054 4.77
2.73E+05 34.3793 4.36
2.58E+05 52.9353 4.99
1.94E+05 78.8070 4.74
1.31E+05 54.6804 6.60
9.62E+04 57.5815 6.55
8.23E+04 72.3524 7.15
7.76E+04 103.4913 13.35
6.24E+04 189.5316 14.33
8.05E+05
6.0591 0.94
4.79E+05 12.0495 1.66
2.79E+05 20.0652 2.59
1.41E+05 35.2611 3.55
7.19E+04 55.4025 5.06

tmean
18.35
18.00
24.81
27.39
29.78
38.05
50.64
63.85
84.42
95.07
95.11
100.39
139.22
220.23
320.20
394.79
438.63
546.97
18.08
37.84
82.90
191.88
455.38

vmean
Emean
Estd
5.45E+05
4.6772 0.26
5.56E+05 8.1511 0.65
4.03E+05 16.2338 0.66
3.65E+05 13.3930 1.80
3.36E+05 14.4350 3.01
2.63E+05 16.5951 3.10
1.98E+05 15.1545 2.79
1.57E+05 18.6434 2.48
1.19E+05 40.6789 4.66
1.05E+05 25.3528 5.30
1.05E+05 32.9423 5.08
9.97E+04 47.6395 5.86
7.19E+04 78.8601 5.69
4.54E+04 55.3668 6.08
3.12E+04 57.3717 6.56
2.53E+04 72.8575 7.87
2.28E+04 101.7607 11.42
1.83E+04 182.2880 16.48
5.53E+05
6.0951 1.09
2.64E+05 11.3298 1.75
1.21E+05 18.3942 2.29
5.21E+04 35.3539 3.02
2.20E+04 55.0803 5.55

tmean
18.35
18.00
24.81
27.39
29.78
38.05
50.64
63.85
84.42
95.07
95.11
100.39
139.22
220.23
320.20
394.79
438.63
546.97
18.08
37.84
82.90
191.88
455.38

tlmt = tmean (DEwls
lscr )
DElscr
vmean
cv
Emean
Estd
7.98E+05 1.46
4.7831 0.26
8.22E+05 1.48
8.1340 0.92
6.72E+05 1.66 16.3452 0.48
6.07E+05 1.66 14.1388 0.54
5.73E+05 1.70 16.7171 1.24
4.97E+05 1.89 18.9328 1.85
4.06E+05 2.06 16.1873 2.34
3.44E+05 2.20 20.2815 1.80
2.92E+05 2.46 46.1607 2.28
2.74E+05 2.61 31.7309 4.26
2.81E+05 2.67 36.7141 4.66
2.66E+05 2.67 56.5688 3.80
2.02E+05 2.82 82.8484 2.14
1.37E+05 3.01 59.9772 5.93
1.03E+05 3.29 63.5027 6.29
9.10E+04 3.59 78.8594 6.17
8.71E+04 3.82 116.0248 11.99
7.14E+04 3.91 205.3507 10.62
8.07E+05 1.46
6.3373 0.83
4.82E+05 1.82 12.8967 1.70
2.87E+05 2.38 21.4521 2.62
1.46E+05 2.80 37.9751 2.44
7.92E+04 3.61 59.1793 4.40

Table 4 The influence of the component reinitialization to the algorithm’s efficiency according to two algorithms: DElscr - with
11
component reinitialization and DEwcr
lscr - without component reinitialization. Two stopping conditions were used: NSE lmt = 10
and target values that were set to the best known energy values (see Table 8). The shown CNSE represents the reduction of
NSE mean : DElscr (NSE mean ) / DEwcr
lscr (NSE mean ).
Label

Length

D

target

1BXP
1CB3
1BXL
1EDP
2ZNF
F13

13
13
16
17
18
13

21
21
27
29
31
21

5.6104
8.4589
17.3962
15.0092
18.3402
6.9961

NSE mean
1.56E+09
3.61E+07
1.24E+10
4.58E+09
2.10E+09
8.92E+07

DElscr
CNSE
NSE std
0.38 1.68E+09
0.18 4.26E+07
< 0.37 1.24E+10
< 0.22 4.21E+09
< 0.05 1.92E+09
0.08 8.52E+07

fore, the speed up factor is dependent on the relationship between the number of solution evaluations inside
and outside the local search. However, using the local
search, the algorithm is capable of obtaining better energy values for almost all sequences, and this improvement of energy values increases for larger sequences.

5.3 Component reinitialization
The main goal of the component reinitialization is to
redirect the evolutionary process in such a way that a
similar good solution can be located according the local best solution. To demonstrate the influence of this
mechanism on the algorithm’s efficiency, the algorithm
was analyzed with (DElscr ) and without (DEwcr
lscr ) component reinitialization. Within this analysis, the algorithms were compared using the target values of the

hitr
100
100
100
100
100
100

NSE mean
4.07E+09
1.99E+08
3.36E+10
2.14E+10
4.31E+10
1.14E+09

DEwcr
lscr
NSE std
4.20E+09
1.77E+08
2.71E+10
2.10E+10
2.75E+10
1.27E+09

hitr
100
100
32
96
50
100

best-known energy values and NSE lmt = 1011 , as shown
in Table 4. The best values of NSE mean and hit r are
marked in bold typeface. From the shown results, we
can find that the algorithm that uses component reinitialization is capable of reaching the best-known energy
value in all runs, and for that it required significantly
less solution evaluations (NSE ). On the other hand,
the algorithm without component reinitialization was
not capable of reaching hit r = 100 within the budget of NSE lmt = 1011 for sequences 1BXL, 1EDP and
2ZNF. From these observations, we can conclude that
the proposed component reinitialization allows the algorithm to locate good similar solutions and to reach
the best-known energy values. This is shown clearly in
Table 4, with CNSE which represents the relationship
between the obtained values of NSE mean for both algorithms. The component reinitialization reduces the

Protein Folding Optimization using DE with Local Search and Component Reinitialization

11

Table 5 Asymptotic average-case performances for DElscr . Values marked with the * are obtained by using the grid environmean
ment. In these cases tmean is calculated as follows: tmean = NSE
, where vmean represents the obtained mean speed of three
vmean
independent runs on our test computer in a given period of time (tlmt = 3600 seconds). All other results are obtained on our
test computer.
Label
1BXP

1CB3

1BXL

1EDP

2ZNF

F13

target
tmean
NSE mean
target
tmean
NSE mean
target
tmean
NSE mean
target
tmean
NSE mean
target
tmean
NSE mean
target
tmean
NSE mean

1
1.8013
0.16
2.45e+05
1.9174
0.06
1.03e+05
11.1862
167.93
8.96e+07
6.3823
677.33
6.74e+08
9.3228
4153.21
3.67e+09
1.8225
0.42
6.62e+05

2
2.0063
10.52
1.38e+07
1.9786
1.01
1.41e+06
13.8397
1472.79
7.07e+08
8.9122
437.82
3.88e+08
12.1166
270.26
2.18e+08
2.0453
3.34
4.52e+06

3
2.6838
395.94
4.62e+08
2.3884
1.67
2.06e+06
13.6386
611.86
2.68e+08
8.7042
1280.42
1.04e+09
11.9772
488.05
3.65e+08
4.6082
4.48
5.20e+06

4
3.1846
1349.36
1.42e+09
4.0429
4.22
4.82e+06
14.0105
508.47
2.14e+08
9.1152
776.01
5.97e+08
12.3307
755.42
5.50e+08
4.6858
8.03
8.43e+06

NSE mean from 0.38 to less than 0.05. Finally, it is obvious that the reinitialization mechanism is responsible
for the DElscr obtaining hit r = 100 for all the sequences
shown in Table 4.
Results show additionally that the value of NSE mean
is not only dependent on the sequence length or problem dimension, but also on the sequence itself. For example, for DElscr the value of NSE mean is 5.9 times
smaller for sequence 2ZNF in comparison with sequence
1BXL, although the dimension of the first sequence is
greater than the dimension of the second sequence.
5.4 Asymptotic average-case performance
In this section, we introduce an approach to determine
asymptotic average-case performance of the algorithm
for small sequences. The condition for this is the ability of the algorithm to obtain the best known solution
with hitr = 100. Until now, only our algorithm is able
to fulfill this condition for the 6 shortest sequences.
Six subsequences are generated for each of these sequences. The first subsequence has removed the last
monomer, the second subsequence has removed the last
two monomers, etc. This means that the length of each
next subsequence is decreased by 1. For example, for sequence 1CB3 (BABBBAABBAAAB) the following six
subsequences are generated:
1.
2.
3.
4.
5.
6.

BABBBAABBAAA (L = 12, target = 8.4088),
BABBBAABBAA (L = 11, target = 6.0209),
BABBBAABBA (L = 10, target = 4.0429),
BABBBAABB (L = 9, target = 2.3884),
BABBBAAB (L = 8, target = 1.9786),
BABBBAA (L = 7, target = 1.9174).

5
4.0191
12.39
1.17e+07
6.0209
4.70
4.52e+06
16.8991
25965.63 *
9.93e+09 *
11.5309
3494.96
2.47e+09
14.6296
562.56
3.77e+08
5.0428
10.47
9.74e+06

6
4.9321
125.70
1.09e+08
8.4088
80.85
7.11e+07
16.9404
113126.9 *
4.05e+10 *
11.7522
922.22
6.27e+08
14.6733
41844.24 *
1.32e+10 *
6.8092
70.98
6.19e+07

7
5.6104
1965.08
1.56e+09
8.4589
44.47
3.61e+07
17.3962
39706.68 *
1.34e+10 *
15.0092
7272.60
4.58e+09
18.3402
7437.15
2.10e+09
6.9961
110.54
8.92e+07

Asymptotic model
0.0015 · 2.8911L
4589.5644 · 2.5970L
0.0001 · 2.8662L
344.4917 · 2.5502L
0.0030 · 2.7931L
6240.7027 · 2.5976L
10.7641 · 1.4097L
2.32e+07 · 1.3103L
16.6030 · 1.3505L
3.19e+07·1.2642L
0.0019 · 2.3266L
6138.4492 · 2.0846L

The best-known or target values are determined for
all subsequences. In our case, we performed one run
for each subsequence with tlmt = 4 days and the best
reached energy value is used as a target value. Using
these target values as a stopping condition, it is possible to calculate asymptotic average-case performance.
The original sequence is also included within this calculation. This means the asymptotic average-case performance is determined by using 7 sequences.
Table 5 and Figure 5 display the target values, obtained mean values and asymptotic average-case performances for DElscr . From the shown results, we observe
that the best asymptotic average-case performances was
obtained for sequence 2ZNF while the worst for sequences 1BXP and 1BXL. We can again observe that
the value of NSEmean and tmean are not only dependent
on the sequence length. Only one monomer can influence these values significantly. For example, DElscr requires less solution evaluations (NSE ) and runtime (t)
to reach the target value for the subsequence of sequence 1EDP that has a length of 16 in comparison
with a subsequence of length 13. From these results, we
can conclude that the structure of the sequence has a
big influence on the difficulty of the problem.

5.5 Comparison with other algorithms
In this section, our algorithm is compared with other algorithms according to two stopping conditions NSElmt
and tlmt , and according to the best obtained energy
values.
The obtained results for stopping conditions NSElmt
that were set according to the literature [4,22] and three

12

11

13

14

15

16

17

12

13

14

20000
5000

observed t mean
model (t mean ) : 16.603 ⋅ 1.3505L
observed NSE mean
model (N S E mean ) : 31907895 ⋅ 1.2642L

●

●

2000

Runtime (t ) [s]

16

●

●

●

●

●

●

7

15

1000

5e+07
2e+07
5e+06

Number of solution evaluations (NSE )

50.0
5.0 10.0
2.0

Runtime (t ) [s]

●
●

1e+06

5e+08

●

●
●

1.0

●

●

●

500

5e+09
2e+09
1e+09

2000
●

observed t mean
model (t mean ) : 0.0019 ⋅ 2.3266L
observed NSE mean
model (N S E mean ) : 6138.449 ⋅ 2.0846L

5e+10

●

10

●

●

●

8

9

10

11

12

13

1e+10
2e+09
5e+08
1e+08

100

13

Number of solution evaluations (NSE )

10000
2000

2e+06

Runtime (t ) [s]

500

1e+07

5e+00

5e+05
11

(c) 1BXL

0.5

5000

10

(b) 1CB3

1000

Runtime (t ) [s]

9

(a) 1BXP

●

500

8

Length (L )

observed t mean
model (t mean ) : 10.7641 ⋅ 1.4097L
observed NSE mean
model (N S E mean ) : 23203404 ⋅ 1.3103L

12

●

7

Length (L )

●

11

●

Length (L )

●

●

●

5e+09

13

●

12

13

14

15

16

Length (L )

Length (L )

Length (L )

(d) 1EDP

(e) F13

(f) 2ZNF

2e+09

12

●

●

5e+08

11

●

●

17

18

Number of solution evaluations (NSE )

10

●

●

●

observed t mean
model (t mean ) : 0.003 ⋅ 2.7931L
observed NSE mean
model (N S E mean ) : 6240.703 ⋅ 2.5976L

2e+08

9

Number of solution evaluations (NSE )

8

●

Number of solution evaluations (NSE )

5e+01

●

7

●

●

1e+05

5e+05

Runtime (t ) [s]

5e+06

5e+00

●

●

observed t mean
model (t mean ) : 1e−04 ⋅ 2.8662L
observed NSE mean
model (N S E mean ) : 344.4917 ⋅ 2.5502L

5e−01

5e+07

5e+01

●

5e−01

Runtime (t ) [s]

●

5e−02

5e+08

5e+02

●

Number of solution evaluations (NSE )

●

●

observed t mean
model (t mean ) : 0.0015 ⋅ 2.8911L
observed NSE●mean
model (N S E mean ) : 4589.564 ⋅ 2.597L

50000

Borko Bošković, Janez Brest

5e+07

12

Fig. 5 Asymptotic average-case performances for DElscr .

algorithms DElscr , DEpfo and BE-ABC are shown in
Table 6. The best obtained energy values are marked in
bold typeface. It can be observed that DElscr and DEpfo
are comparable, and both outperform BE-ABC. Results
that take into account speed up factor (see Table 3) are
shown in the last column of the table. In this case, both
algorithms DElscr and DEpfo spend approximately the
same amount of runtime, and DElscr outperforms DEpfo
on most sequences.
Within this comparison, the value of NSElmt was
relatively small. This means the reinitialization mechanism within DEpfo did not have a significant impact on
the obtained results. Therefore, DEpfo and DElscr were
also compared according to the tlmt that was set to 4
days. A grid environment was used within this comparison and results are shown in Table 7. In this comparison, DElscr obtained better values of Emean , Ebest and
hitr in most sequences, and equal values for the shortest
sequences. DElscr obtained hitr of 100, 100, 19 and 65
for shorter sequences 1BXL, 1EDP, 2H3S and F21. For

the same sequences, DEpfo obtained hitr of 6.67, 13.33, 0
and 0, respectively. Significant improvement was obtained for longer sequences too. For example, the best
energy values were improved from 90.914, 131.7787 and
225.0968 to 106.419, 156.525 and 245.519 for sequences
1GK4, 1PCH and 2EWH. The energy values were improved by 15.505, 24.7463 and 20.4222. Note that DElscr
obtained the new best known solutions for all sequences
with L ≥ 18, the hitr = 100 for 6 shortest sequences
and hitr > 1 for 9 sequences by using tlmt = 4 days.
The most important results in this paper are shown
in Table 8, which collects the best energy values from all
experiments that were described in previous sections,
and the best-known energy values from the literature.
It is evident that DElscr confirmed the best known energy values for the 3 shortest sequences, and reached the
new best-known energy values for all other sequences,
except for sequence F13. Solutions for the best energy
values reached by DElscr are shown in Tables 9 and 10.
In [19] an efficient global optimization method is ap-

Protein Folding Optimization using DE with Local Search and Component Reinitialization

13

Table 6 Comparison of the DElscr algorithm with state-of-the-art algorithms.
Label

M

1CB3
1BXL
1EDP
2H3S
2KGU
1TZ4
1TZ5
1AGT
1CRN
1HVV
1GK4
1PCH
2EWH
F13
F21
F34
F55

20
20
20
20
20
20
20
20
20
20
20
80
80
4
4
12
20

Ebest
7.7450
16.2618
13.1764
17.1724
41.0221
34.5265
37.8896
49.9861
74.7849
45.0054
49.9316
121.0579
193.8143
4.9533
11.1304
19.9550
29.5163

DElscr
Emean
4.5108
12.5045
8.1986
11.5310
33.6539
21.6863
25.9996
39.1897
62.2668
35.9335
42.0261
87.5748
162.3482
3.0907
6.5538
13.3057
22.4019

Estd
2.13
2.17
2.78
2.45
3.99
3.62
4.12
5.21
7.60
4.92
4.77
11.42
16.60
0.78
1.53
2.47
3.58

NSElmt = M · 104
DEpfo [4]
Ebest
Emean
Estd
8.3690
5.5884
1.96
16.3443
12.6104
2.53
13.5620
8.6666
2.56
16.5030
10.6767
2.75
44.3369
35.3850
4.70
30.9211
20.4361
5.28
38.1868
27.3412
4.08
50.6311
39.0268
5.34
74.4068
60.2444
7.58
44.7264
34.8059
5.29
52.0651
44.8591
4.72
103.1776
79.4878
8.85
171.6390 144.9060 12.84
5.7290
3.6040
0.66
11.2211
7.9567
1.53
19.3529
14.0749
2.09
31.9554
24.6243
3.57

BE-ABC [22, 23]
Ebest
Emean
Estd
– 5.9417 0.78
– 11.6942 1.13
–
8.0500 0.93
– 10.4618 1.13
– 22.7195 2.01
– 14.9436 2.22
– 17.4859 1.37
– 25.6024 2.34
– 42.3083 2.96
– 21.5386 3.53
– 27.0410 3.24
– 51.6674 3.50
– 94.5785 5.70
3.3945
2.8196 0.38
6.9065
5.2674 0.76
10.4224
8.3239 0.92
18.8385 14.4556 1.56

NSElmt = M · 104 · cv
DElscr
Ebest
Emean
Estd
7.7450
4.5929
2.16
16.7137
13.1940
2.22
13.1895
8.5313
2.81
17.4858
11.9565
2.48
44.0110
36.4642
4.39
35.3505
24.9569
4.55
40.0161
28.9335
3.60
54.0897
43.4210
5.45
82.5999
68.3890
7.28
57.1990
46.3685
5.61
69.5798
56.6853
5.16
128.4882
99.3441 14.52
210.7021 181.5912 17.49
4.9704
3.1977
0.79
11.7522
7.6885
1.75
21.0345
15.4491
2.85
33.1788
26.8111
3.34

Table 7 The obtained results for DElscr and DEpfo within a runtime limit of 4 days.
Label

L

1BXP
1CB3
1BXL
1EDP
2ZNF
1EDN
2H3S
1ARE
2KGU
1TZ4
1TZ5
1AGT
1CRN
2KAP
1HVV
1GK4
1PCH
2EWH
F13
F21
F34
F55
F89

13
13
16
17
18
21
25
29
34
37
37
38
46
60
75
84
88
98
13
21
34
55
89

DElscr , number of independent runs N=100
Ebest
Emean
Estd
hitr
5.6104
5.6104 0.0000
100.00
8.4589
8.4589 0.0000
100.00
17.3962
17.3962 0.0000
100.00
15.0092
15.0092 0.0000
100.00
18.3402
18.3402 0.0000
100.00
21.4703
21.3669 0.0431
7.00
21.1519
20.9956 0.0995
19.00
25.2800
24.5444 0.1718
1.00
52.7165
51.7233 0.3829
1.00
43.0229
41.8734 0.4285
1.00
49.3868
48.6399 0.3292
1.00
65.1990
64.1285 0.4173
1.00
92.9853
89.8223 0.6514
1.00
85.5099
83.1503 1.0041
1.00
95.4475
91.4531 1.9215
1.00
106.4190
99.6704 3.0377
1.00
156.5250 153.1003 2.7117
1.00
245.5190 240.2247 2.1421
1.00
6.9961
6.9961 0.0000
100.00
16.5544
16.5304 0.0329
65.00
31.3455
30.4913 0.3458
1.00
51.9030
49.5009 0.8817
1.00
81.5297
76.4804 2.0603
1.00

plied to the sequence F89. Within this work, 32,200
distinct conformations were obtained, and the best obtained energy was 73.1065. DElscr improves this energy
by 10.4695.

5.6 Analysis of the obtained structures
For most of the sequences, the best conformations were
obtained by using tlmt = 4 days. Within this experiment, 100 solutions were generated with 100 independent runs. Distribution of the Root-Mean-Square Error
(RMSE) values as a function of energy for all these solutions according to the best-known conformation for

DEpfo [4], number of independent runs N=30
Ebest
Emean
Estd
hitr
–
–
–
–
8.4589
8.4589 0.0000
100.00
17.3962
17.1916 0.0878
6.67
15.0092
14.9423 0.0471
13.33
–
–
–
–
–
–
–
–
20.0979
19.6147 0.2699
0.00
–
–
–
–
50.2960
49.1661 0.6334
0.00
39.7340
37.8329 0.9983
0.00
47.1513
43.9959 1.4087
0.00
62.8951
60.4175 1.0439
0.00
89.2001
86.0390 1.4529
0.00
–
–
–
–
82.1427
68.8332 4.0852
0.00
90.9140
84.6836 3.3356
0.00
131.7787 117.7603 6.2617
0.00
225.0968 203.6813 7.1844
0.00
6.9961
6.9961 0.0000
100.00
16.2250
15.8894 0.1849
0.00
28.2509
25.6602 1.0523
0.00
45.0942
41.8670 1.4693
0.00
–
–
–
–

selected sequences is shown in Fig. 6. Note that the
RMSE is calculated by using the superposition between
matched pairs. From Fig. 6a, we can see that only two
different solutions were reached for sequence 2ZNF. Similar graphs with only two different solutions were obtained for 6 sequences where hitr = 100 (see Table 7).
Three-dimensional representations of these solutions are
displayed in Fig. 7. As is shown, for each of these sequences two solutions are symmetrical according to the
XY-plane. This can also be seen from Tables 9 and 10.
Two reported solutions for one sequence are very similar. They are different in some components that belong
to β torsional angles (marked in bold typeface), and

14

Borko Bošković, Janez Brest

Table 8 Comparisons of the best energy values reported in the literature and the best energy values obtained by DElscr . The
solution vectors obtained by DElscr are shown in Tables 9 and 10.
Label

DElscr

1BXP
1CB3
1BXL
1EDP
2ZNF
1EDN
2H3S
1ARE
2KGU
1TZ4
1TZ5
1AGT
1CRN
2KAP
1HVV
1GK4
1PCH
2EWH
F13
F21
F34
F55
F89

5.6104
8.4589
17.3962
15.0092
18.3402
21.4703
21.1519
25.2800
52.7165
43.0229
49.3868
65.1990
92.9853
85.5099
95.4475
106.4193
156.5252
245.5193
6.9961
16.5544
31.3459
52.0558
83.5761

DEpfo
[4]
–
8.4589
17.3962
15.0092
–
–
20.0979
–
50.2960
39.7340
47.1513
62.8951
89.2001
–
82.1427
90.9140
131.779
225.097
6.9961
16.2250
28.2509
45.0942
–

ImHS
[15]
4.498
–
15.200
–
15.056
17.721
15.340
17.416
40.696
–
–
40.300
61.426
44.972
–
–
–
–
–
–
–
–
–

BE-ABC
[22, 23]
2.8930
8.4580
15.9261
13.9276
5.8150
7.6890
18.3299
10.2580
28.1423
39.4901
45.3233
51.8019
54.7253
27.1400
47.4484
49.4871
91.3508
146.8231
6.9961
15.6258
28.0516
42.5814
–

I-PSO
[9]
–
–
–
–
–
–
–
–
20.9633
–
–
–
28.7591
15.9988
–
–
46.4964
–
–
–
–
–
–

their values represent angles with opposite directions.
For a little bit longer sequences more different solutions
were reached with different energy values, as shown in
Figs. 6b and 6c while, for the longest sequences, all
100 solutions are different with different energy values.
For example, this is illustrated in Fig. 6d for sequence
2EWH. From these results, we can conclude that all
reported symmetrical solutions could be optimal, especially those obtained with hitr = 100, and all other
solutions with hitr = 1 are almost surely not optimal.
6 Conclusions
In this paper, we presented a novel differential evolution
algorithm for protein folding optimization. To improve
its efficiency, the algorithm is extended with a component reinitialization and local search that includes a
local movement. The component reinitialization is designed to redirect the search process to similar solutions
that are different from the already found good solution in only a few components. Thus, the search space
around good solutions is explored thoroughly and, consequently, the algorithm can find better solutions. We
also designed the local movement for a three-dimensional
AB-off lattice model in such a way that only a two
consecutive monomers are moved locally while all the
remaining monomers remain in their positions. With
additional data structure this type of movement allows
us to reduce the runtime complexity of the energy cal-

PGATS
[41]
–
–
–
–
–
–
–
–
32.2599
–
–
–
49.6487
28.1052
–
–
49.5729
–
–
–
–
–
–

MPGPSO
[42]
–
–
–
–
–
–
–
–
–
–
–
–
43.9339
18.9513
–
–
38.2766
–
–
–
–
–
–

ABC
[24]
–
–
–
–
–
–
–
–
31.9480
–
–
–
52.3249
30.3643
–
–
63.4272
–
–
–
–
–
–

GATS
[35, 36]
–
8.2515
15.8246
13.7769
–
–
18.1640
–
–
39.3444
45.3019
46.0842
–
25.1003
–
–
–
–
6.9539
14.7974
27.9897
42.4746
–
2

C-ABC
[37]
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
7.0025
14.9570
28.0055
42.2769
–

culation within the local search from L2 to 2L. The 23
sequences are used in the experiments to analyze the
proposed algorithm and its mechanisms.
From the results of the algorithms with and without
local search, it is evident that the local movement with
additional data structure reduces the runtime complexity of the energy calculation, or increases the number of
function evaluations per second by factor 1.46 for the
shortest sequences, and by factor 3.91 for the longest sequence. This speed up is dependent on sequence length
and the relationship between the number of solution
evaluations inside and outside the local search. The local search also improves the algorithm’s convergence
speed for most of the sequences. Because of both advantages, the local search improves the efficiency of the
algorithm, and this improvement is greater for longer
sequences.
Using the best-known energy values as a stopping
condition, we demonstrated the usefulness of component reinitialization. It reduces the required mean number of solution evaluations to reach the best-known energy value from 0.38 to less than 0.05. This indicates
that the component reinitialization redirects the search
process successfully to similar solutions, and allows the
algorithm to locate the best-known solutions efficiently.
Our algorithm is the first algorithm that is capable of obtaining a hit ratio of 100 % for 6 shorter sequences within the budget of 1011 function evaluations.
Therefore, we introduce an approach for determining

Protein Folding Optimization using DE with Local Search and Component Reinitialization

●

0.0

0.2

0.4

0.6
RMSE

●
●

(a) 2ZNF

1.0

●

●

●

●

the best obtained solution
the obtained soluton
●

0.0

0.5

1.0

1.5

RMSE

(b) 1EDN

244
●

●

●
●●

● ●

●

●

●

0.0

the best obtained solution
the obtained soluton ● ●
0.2

0.4

0.6 0.8
RMSE

(c) 2H3S

●

●

●

●

●

●●

Energy (E)
240
242

●

●

●

0.8

●
●

20.90

21.30
●

the best obtained solution
the obtained soluton

21.25

●

●

●●

●

●

●

238

●
●

●

●●● ●

236

●

●

●

Energy (E)
21.00

●

20.80

●

●

●

21.10

21.45

●

Energy (E)
21.35 21.40

●

15

Energy (E)
20

25

●

15

●

1.0

●
●

●
●
●
●
●
● ●
● ●
● ●
●
●
●
● ● ●●
●
●
●●
● ●●● ●● ● ●
●
● ● ●● ●●
●
●
●●●
●
●
●
●
●
●
●
●
●
●● ● ● ●
●
● ●
●
●
● ●● ●●
● ●
● ●
●
●●
●●
●● ●
● ●●
●
●
●
●
●
●
●● ● ●
●
●

the best obtained solution
the obtained soluton

●

1.2

●

●

1.4

0.0

0.5

1.0

1.5
RMSE

2.0

2.5

(d) 2EWH

Fig. 6 Distribution of the Root-Mean-Square Error (RMSE) values as a function of energy for all 100 obtained conformations
within runtime limit of 4 days, calculated from the best-known conformation.

asymptotic average-case performances. Our algorithm
obtained the best runtime asymptotic average-case performance for sequence 2ZNF (16.6030 · 1.3505L ) and
the worst for 1BXP (0.0015 · 2.8911L ). This approach
shows additionally that the difficulty of the problem is
not only dependent on sequence length, but also on the
sequence itself.
The proposed algorithm was also compared with recently published state-of-the-art algorithms for PFO. It
outperforms all competitors, and the obtained energy
values improve the best-known energy values from the
literature for all sequences with L ≥ 18. For example,
the best energy value of sequence 1PCH was improved
from 131.7787 to 156.5250 or by 24.7463.
The structure of the best obtained solutions was also
analyzed. We figured out that there exist two symmetric best-known solutions for sequences with L ≤ 25.
For these sequences, our algorithm obtained a hit ratio
equal to or greater than 7 %. The solutions of these
sequences could be optimal, especially those with a hit
ratio of 100 %, and solutions for all other sequences are
almost surely not optimal.
In the future work we will try to improve the algorithm further by using knowledge about symmetric
solutions. This knowledge can be integrated within the
evaluation function, or used to reduce the size of the
search space. Additionally, we will try to design an algorithm that will reduce the likelihood of the exploration
of already explored search space.

Acknowledgements
Our work was supported by the Slovenian Research
Agency under Program P2-0041 (Computer Systems,
Methodologies, and Intelligent Services).

References
1. Alberts, B., Bray, D., Hopkin, K., Johnson, A.D., Lewis,
J., Raff, M., Roberts, K., Walter, P.: Essential Cell Biology, 4 edn. Garland Science (2013)
2. Balchin, D., Hayer-Hartl, M., Hartl, F.U.: In vivo aspects
of protein folding and quality control. Science 353(6294)
(2016). doi:10.1126/science.aac4354
3. Bazzoli, A., Tettamanzi, A.G.B.: A Memetic Algorithm
for Protein Structure Prediction in a 3D-Lattice HP
Model. In: G.R. Raidl, S. Cagnoni, J. Branke, D.W.
Corne, R. Drechsler, Y. Jin, C.G. Johnson, P. Machado,
E. Marchiori, F. Rothlauf, G.D. Smith, G. Squillero (eds.)
Applications of Evolutionary Computing, Lecture Notes
in Computer Science, vol. 3005, pp. 1–10. Springer Berlin
Heidelberg (2004). doi:10.1007/978-3-540-24653-4 1
4. Bošković, B., Brest, J.: Differential evolution for protein
folding optimization based on a three-dimensional AB
off-lattice model. Journal of Molecular Modeling 22, 1–
15 (2016). doi:10.1007/s00894-016-3104-z
5. Bošković, B., Brest, J.: Genetic Algorithm with Advanced Mechanisms Applied to the Protein Structure
Prediction in a Hydrophobic-Polar Model and Cubic
Lattice. Applied Soft Computing 45, 61–70 (2016).
doi:10.1016/j.asoc.2016.04.001
6. Brest, J., Greiner, S., Bošković, B., Mernik, M., Žumer,
V.: Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark
Problems. IEEE Trans. Evol. Comput 10(6), 646–657
(2006). doi:10.1109/TEVC.2006.872133
7. Buxbaum, E.: Fundamentals of Protein Structure and
Function. Springer US (2007)
8. Chen, M., Huang, W.q.: Heuristic algorithm for offlattice protein folding problem.
Journal of Zhejiang University SCIENCE B 7(1), 7–12 (2006).
doi:10.1631/jzus.2006.B0007
9. Chen, X., Lv, M., Zhao, L., Zhang, X.: An Improved Particle Swarm Optimization for Protein Folding Prediction. International Journal of Information
Engineering and Electronic Business 3(1), 1–8 (2011).
doi:10.5815/ijieeb.2011.01.01
10. Denning, P.J.: The Locality Principle. Commun. ACM
48(7), 19–24 (2005). doi:10.1145/1070838.1070856
11. Fraenkel, A.S.: Complexity of protein folding. Bulletin of Mathematical Biology 55(6), 1199–1210 (1993).
doi:10.1007/BF02460704

16

Borko Bošković, Janez Brest

Table 9 The best solutions obtained by the DElscr algorithm.
Label
1BXP
1BXP

Solution vector in degrees
43.2915, 2.88166, -48.728, 0.0655009, 12.6242, 66.0927, -6.40805, 8.96332, 8.80015, 2.23544, 74.0763, -6.62061, 1.31798, -104.099, 160.341,
-177.384, -20.6892, 26.8003, 127.789, 166.27, 10.2979
43.2915, 2.88166, -48.728, 0.0654961, 12.6242, 66.0927, -6.40805, 8.96332, 8.80016, 2.23544, 74.0763, 6.62061, -1.31798, 104.099, -160.341,
177.384, 20.6892, -26.8003, -127.789, -166.27, -10.2979

1CB3

-14.0758, 25.2546, -38.7359, -9.58086, 21.0366, 14.7617, -0.998265, 21.5393, 71.2738, -27.6012, -5.16526, -19.1483, -149.775, 172.54, 178.086,
178.164, 91.6772, 4.85452, -31.1093, 28.9806, 3.41538

1CB3

-14.0758, 25.2546, -38.7359, -9.58086, 21.0366, 14.7617, -0.998265, 21.5393, 71.2738, -27.6012, -5.16526, 19.1483, 149.775, -172.54, -178.086,
-178.164, -91.6772, -4.85451, 31.1093, -28.9806, -3.41538

1BXL

-22.4292, -32.2737, -16.9254, 5.81295, 15.6175, 26.9979, -38.2372, 52.8361, -48.2442, -24.0736, 49.3335, -36.1178, 13.9215, 12.5486, 1.91872,
55.1452, 147.302, -127.63, 168.592, -62.9624, -27.0891, 28.7221, 27.4283, 152.122, -177.152, 67.7357, -5.21217

1BXL

-22.4292, -32.2737, -16.9254, 5.81296, 15.6175, 26.9979, -38.2372, 52.8361, -48.2442, -24.0736, 49.3335, -36.1178, 13.9215, 12.5486, -1.91872,
-55.1452, -147.302, 127.63, -168.592, 62.9624, 27.0891, -28.7221, -27.4283, -152.122, 177.152, -67.7357, 5.21217

1EDP

-22.6336, 7.26974, 60.7674, 23.936, -50.4261, 4.41672, 11.4886, 46.499, 13.2306, -12.2668, 22.7087, 4.07035, 30.6245, -69.1251, 16.9542, 26.0209,
124.911, -155.575, -61.088, 1.55078, 53.7379, 159.421, -162.592, -156.44, -170.499, -85.1224, 2.36332, -25.7677, 67.3571

1EDP

-22.6336, 7.26974, 60.7674, 23.9359, -50.4261, 4.41671, 11.4886, 46.499,13.2306, -12.2668, 22.7087, 4.07036, 30.6245, -69.1251, 16.9542, -26.0209,
-124.911, 155.575, 61.088, -1.55077, -53.7379, -159.421, 162.592, 156.44, 170.499, 85.1224, -2.36333, 25.7677, -67.3571

2ZNF

-22.512, 7.71692, -75.1038, 26.0695, 35.539, 19.645, 6.73951, 21.8104, -57.4641, 1.6924, 6.15567, 3.08902, 9.89786, 23.8155, -48.9192, -4.31387,
78.7078, 2.66583, -114.943, -148.187, -162.564, -79.1176, 8.87759, -178.428, 42.9368, 15.8392, -18.6691, -104.193, 166.46, 12.876,
140.107

2ZNF

-22.512 7.71691, -75.1038, 26.0694, 35.539, 19.645, 6.73952, 21.8104, -57.4641, 1.6924, 6.15567, 3.08903, 9.89787, 23.8155, -48.9192, -4.31386,
-78.7078, -2.66582, 114.943, 148.187, 162.564, 79.1176, -8.87759, 178.428, -42.9368, -15.8392, 18.6691, 104.193, -166.46, -12.876,
-140.107

1EDN

-23.2048, 31.2208, 46.764, 48.9339, -43.6867, -28.0164, -17.6723, -38.3711, -25.1772, 10.6263, 9.07757, 33.5364, -4.83762, -6.09916, 25.0581, -81.151,
15.5944, -3.62479, -36.6783, 41.0025, 127.461, -147.732, -53.6249, -22.4102, -68.6344, -166.972, 147.028, -171.451, -155.381, 121.71,
29.6786, 131.144, 15.2983, 24.5428, -54.7787, -83.2637, -29.6805

1EDN

-23.2048, 31.2207, 46.764, 48.9338, -43.6867, -28.0164, -17.6723, -38.3711, -25.1772, 10.6262, 9.07754, 33.5364, -4.83764, -6.09917, 25.058, -81.151,
15.5944, -3.62479, -36.6783, -41.0025, -127.461, 147.732, 53.6249, 22.4102, 68.6344, 166.972, -147.028, 171.451, 155.381, -121.71,
-29.6786, -131.144, -15.2983, -24.5428, 54.7786, 83.2637, 29.6805

2H3S

30.6395, -51.1361, 34.4028, -0.410148, -32.439, -10.4102, -2.09416, 12.4798, -5.74202, -60.0842, 12.6704, -8.68551, -36.5963, -14.4828, -17.9172,
13.0794, 0.148026, 17.7335, -6.06512, 1.46386, -69.7022, 3.0363, 36.2347, -57.1061, -174.679, 173.256, -170.68, -156.724, 142.58, 40.6316,
22.5668, -1.4454, 175.849, -114.818, -61.1893, -4.11275, -27.6809, 84.4735, 144.867, 176.731, 161.605, -97.3254, -158.173, 113.225,
54.3451

2H3S

30.6395, -51.1361, 34.4028, -0.410146, -32.439, -10.4102, -2.09415, 12.4798, -5.74202, -60.0842, 12.6704, -8.68551, -36.5963, -14.4828, -17.9172,
13.0794, 0.148029, 17.7335, -6.06512, 1.46387, -69.7022, 3.0363, 36.2347, 57.1061, 174.679, -173.256, 170.68, 156.724, -142.58, -40.6317,
-22.5668, 1.44539, -175.849, 114.818, 61.1893, 4.11273, 27.6808, -84.4735, -144.867, -176.731, -161.605, 97.3254, 158.173,
-113.225, -54.3451

1ARE

-11.5547, -1.31888, -15.2569, -42.6589, 17.4763, 5.06218, 14.6442, 24.251, 2.4936, -13.6942, 28.8183, -37.0023, -1.8785, -0.867767, -5.02831, 35.1061,
-45.2208, -7.89329, 3.88011, -1.06756, -41.5237, 42.6134, 14.078, 1.71866, -70.4096, 19.7351, 23.088, -23.8173, -48.341, -27.8178, -175.825, 102.429,
138.697, -140.149, -46.4258, -148.917, -22.129, -165.228, 134.775, 48.8091, -12.7742, -50.1159, -163.389, 154.413, 126.397, -131.045, -60.8471,
167.884, 102.299, 52.433, -15.9838, -113.979, -58.9094

2KGU

-156.228, 84.3317, -1.89424, -22.9614, 4.96104, -10.8986, 42.0037, -54.9878, -4.36371, -80.394, 6.84565, -4.01855, -29.0786, 38.404, -24.9304, 51.317,
-53.2373, 15.7134, -51.9703, 1.34405, 37.6371, 36.5939, 35.6007, -52.9444, 32.6405, -108.259, -56.7621, 71.7249, 5.9403, 4.99762, 0.0626093, 8.48403,
-161.728, -140.31, 137.06, 46.113, 21.1367, 45.0214, -27.4148, 37.097, -8.18763, -148.71, 107.671, -141.471, -176.445, 152.171, -23.7168, -63.0744,
-154.472, 9.04166, -89.3673, 21.6149, -71.4051, 41.2427, -22.0274, 113.616, 22.7052, 159.166, -13.0884, -8.78814, 19.7018, 51.7085, 100.664

1TZ4

-13.2782, 2.2117, -21.4873, 13.5614, -50.9456, -18.6314, 58.273, 35.906, -51.557, 43.4606, 14.4093, 26.9361, -9.90087, 51.937, 12.5408, -12.0182,
-39.4559, -3.12819, -37.7837, 39.5619, 14.5525, -105.659, -2.39298, 23.2026, 13.2624, 7.00485, -63.913, 21.5608, -2.32347, -4.49988, 14.2846, -2.28795,
25.5405, -52.7743, -3.52791, 88.4618, 172.62, 63.4655, 167.01, -112.19, -129.059, 165.903, 161.114, -13.1829, -29.6599, -142.278, -118.354, -17.9561,
62.8846, 132.227, 150.392, 59.2519, -21.0203, -51.4332, 27.3873, 6.73164, 10.4224, -36.4599, -134.654, -177.842, -46.6888, 152.495, 60.1706, -2.02398,
-21.7416, 80.9012, 145.281, -5.47398, -93.0592

1TZ5

19.2916, -25.4743, 37.9748, -2.24909, -71.5607, -62.5534, -1.20914, 60.5119, -37.8385, 56.051, -23.4795, 88.5824, -23.4208, 9.88257, -27.3279, 2.64366,
4.72144, -32.8121, -37.9781, 28.6777, -1.79099, -1.45295, -1.55722, -28.7841, 53.5811, -7.1834, 28.1114, -34.8815, -63.6796, -10.3914, 19.0723,
-11.8679, -27.892, -37.0612, 62.2441, 52.8494, -172.157, 163.821, 57.7857, -56.1207, -158.293, 168.377, -23.9122, -20.1987, 4.84453, -2.90382,
-36.4027, -130.461, 158.501, 160.429, -146.987, -129.731, 128.236, 34.5188, 28.0746, -55.2047, -137.136, -167.33, 32.699, 35.1309, -64.3505, 35.5609,
22.6136, -27.8717, -112.09, 160.134, -131.465, -173.819, -165.595

1AGT

26.1664, -11.7847, -37.6783, -3.62257, 75.6542, -40.6386, 24.7245, -92.2268, -13.2317, 23.7859, -94.496, -2.2422, 17.0125, 1.77619, -39.6216, 113.613,
89.2441, -4.72246, -98.3805, -65.8427, 44.1904, -17.7537, -84.2295, -2.33273, -55.9952, -46.6065, -1.4073, 40.7682, -24.0458, 37.5641, 44.8005,
-1.59772, 9.28805, 12.0621, -52.5228, 21.2213, 120.34, -179.746, -63.7778, 18.8875, 10.4973, -6.76493, -21.1687, 57.2819, 176.355, 27.0186, -122.011,
-33.6896, -59.127, -178.6, 14.4172, -4.50249, -165.323, -6.2693, 12.6379, -54.0356, -62.0563, 7.63468, 127.685, 19.1897, 133.256, -157.687, -140.601,
-147.971, -19.8046, 48.3979, 166.316, 54.8275, 156.099, 3.00416, -140.869

1CRN

36.2044, -2.8726, -58.3456, -109.168, 67.0176, 63.8303, -34.4202, -9.13991, 27.0952, 6.87578, -175.904, -10.0323, -14.0642, 169.202, 139.54, 37.4324,
-30.2161, 3.47033, 120.567, 8.05841, 74.7893, -51.1755, -78.2244, -6.56336, -37.0077, -0.404044, 22.8391, -11.2627, -2.90337, -113.857, -122.645,
-5.62342, 80.5936, -19.4761, 87.9704, 12.3212, -4.15216, 3.25955, 39.0676, 30.3454, 61.9086, 12.9802, -97.5976, 8.44839, -76.9107, 30.3312, 41.3065,
24.8161, -34.1801, 20.2024, 33.4227, -14.1966, 80.1988, 28.2782, -166.287, -129.879, -11.8488, 19.3045, -66.9439, -48.3743, -164.938, -12.7803, 7.1584,
29.2233, 12.4003, 39.0045, -58.1443, 52.0717, 43.5443, -0.577219, -103.851, -146.583, -9.20535, -12.6377, -128.769, 27.4049, -32.4672, 16.7912,
-135.646, -149.836, 98.1608, 22.2995, 23.6538, 11.9513, 104.699, -3.17593, 35.9215

2KAP

46.469, 9.17062, -12.987, -39.265, -23.0536, 170.718, 7.46538, -139.561, 9.6654, -109.874, 39.7501, -77.1224, -8.16555, 82.4941, -21.6873, 93.4429,
-10.6347, 10.7423, 20.8323, -4.45369, -11.4409, -5.20606, 147.482, 172.455, -52.8927, 8.19366, 92.0005, -44.9143, -45.2074, -1.91882, -16.8158,
4.77317, 17.6662, 124.018, 11.9037, -1.64667, 74.9571, 15.2233, -5.48327, -140.99, 19.2716, 15.4203, -48.7429, -34.6525, 5.87344, -6.16017, 41.6324,
-16.8426, 49.2516, -28.6507, 29.562, -13.1308, 17.3443, -61.6342, 8.11077, -104.361, 26.4602, 4.19116, 18.9505, 67.8863, 154.188, -116.346, 19.3865,
-84.7317, -27.0054, -31.7152, -24.4805, -34.1621, -13.632, 63.0618, 8.2678, -2.60225, 37.1772, -9.33353, -46.953, -117.05, -167.457, 155.733, -103.59,
35.8403, 44.471, -168.41, -18.09, 28.324, 22.7177, -44.4081, -37.3318, -3.25116, 42.16, 57.0729, -4.27289, -157.026, 158.794, -19.8247, 37.3666,
142.492, -5.84281, 168.076, -163.22, -4.06088, -38.3009, 6.22285, -20.4278, 52.41, 156.856, 11.6928, 124.907, -164.531, 100.594, -172.86, -66.3312,
-55.802, 13.087, 38.8668, 61.5511

Protein Folding Optimization using DE with Local Search and Component Reinitialization

17

Table 10 The best solutions obtained by the DElscr algorithm.
1HVV

123.296, 175.071, -104.639, -8.91165, 17.898, 3.71452, 16.7371, -6.98533, -76.7403, -9.21776, 75.2042, 124.487, 46.9457, 18.594, -46.3806, 145.54,
124.742, -1.01034, 2.75056, 10.5349, -7.0204, 118.317, 75.4052, -30.5719, 69.7023, -72.9042, 176.87, -87.9407, -48.7546, 88.4046, -11.7349, 44.1027,
-5.14578, -65.6298, 20.3053, -20.9559, -72.1726, 94.427, 45.6623, -45.1943, 55.0226, 121.96, 34.0003, 6.44231, 140.467, 17.4955, 85.266, -21.9109,
-95.2265, -24.295, 2.64738, -17.4667, 155.115, -5.99421, -158.933, -6.23019, -43.4673, -28.7354, -11.6413, -19.2361, -10.0374, 34.4593, -178.973,
-160.129, -42.443, 5.40211, -87.2981, -36.4155, 10.9084, 64.5935, -5.14139, 28.5554, -18.3091, -3.52734, 45.1155, 9.74914, 114.875, 75.0862, 26.4021,
22.7921, -63.2735, -138.233, -64.6958, -1.96622, 99.8458, -16.8097, 71.6329, 28.1128, -43.4581, -82.0519, 173.534, -96.2117, -16.7565, -32.4898,
48.5607, 11.8749, -64.2088, 1.38784, -57.9374, 25.3469, 54.5768, 34.603, -28.9913, -102.93, -64.0207, -23.3654, 157.688, 118.979, 5.08255, 61.9001,
-18.6156, -45.7361, -10.7387, 47.8304, -26.517, -104.738, 22.5679, 115.444, -6.44774, 116.951, 14.5305, -0.364305, 25.7291, 114.23, -22.2869, 97.1472,
0.163606, -93.1095, -14.0922, 67.6929, 103.708, 12.5582, -62.8467, -103.687, -55.8599, 11.7904, 63.4791, 74.9204, 26.812, -72.0632, -116.517, -46.752,
39.4218, 63.2466, 101.367

1GK4

-156.276, -11.1754, -77.6765, -33.983, -9.25845, 27.2496, -22.3371, 55.198, -12.6002, 30.4017, 35.9669, -18.5758, -87.0091, 63.2376, 163.731,
-40.6359, 102.397, 146.119, -16.2788, 0.676412, 169.967, -18.769, -43.9974, -62.1645, -51.3378, -148.518, 144.287, -170.774, -25.6785, -22.1326,
27.6078, -8.93322, -75.4448, -68.3403, -16.5373, -128.752, 53.7389, -140.548, -115.598, -1.7515, -106.07, -14.6299, 82.7281, -28.3651, 36.138, 37.748,
-23.152, -11.6747, 20.0652, -55.0055, -150.457, -49.5769, 23.078, 65.4316, 111.217, 34.2085, 8.50149, 21.775, -107.598, 139.532, -69.7933, 68.8643,
88.8784, -166.542, -174.708, 31.9934, 137.315, -3.2063, -88.0773, -6.44718, 23.1364, 95.4164, -34.9923, 2.63385, 13.9679, -23.3478, -54.8455, 43.5591,
-4.20436, -43.6293, -144.761, 18.6453, 179.845, -29.3419, 34.6059, 116.989, -2.74396, 108.058, 157.394, 13.5671, -34.673, -71.5358, 29.1635, -12.3351,
-58.4977, -28.7525, -42.495, -47.6578, 29.0888, -101.645, -92.0769, 10.8024, 101.05, 70.2237, 17.3966, -48.5046, 27.4408, 61.4589, 71.0815, 77.6142,
36.2921, -18.009, -121.503, -122.087, -32.2391, 9.22399, 11.065, 70.686, 48.1796, -38.5792, -91.5736, 15.5793, -173.479, -25.563, 108.153, 54.9784,
-50.888, -86.9754, -52.2761, -23.2842, 20.5012, 16.6481, -23.1703, -40.3118, -64.6739, 26.9541, 177.66, 154.029, 125.888, 2.61904, -11.91, -67.2757,
7.45577, 48.5355, -2.84037, -62.5508, -1.94643, 7.24978, 48.2981, 62.3802, 127.482, 80.9534, -6.93496, -105.181, -59.8353, -45.6067, -113.32, 1.58149,
-33.4263, -8.31888, 28.5097, -8.75938, 151.901

1PCH

41.1106, -75.4478, -108.35, -88.2808, 52.6905, 63.9346, 98.575, -146.011, -103.251, -81.3915, -7.97873, -5.67391, -138.034, 77.0572, -3.43666,
-168.458, -44.1355, -51.9614, -0.548426, -11.6916, -13.85, -90.7331, 162.157, -85.119, -80.3963, 2.41355, -4.42424, 54.2753, 89.5966, -147.035, 78.814,
99.0202, -89.7149, -126.891, -85.1937, 16.9404, -73.4292, 66.5445, 160.832, 40.1368, 145.935, 17.6023, -17.2377, 45.6224, 136.733, -49.815, -43.4151,
-102.65, 8.11703, -109.171, -24.407, -47.2699, -132.484, -42.5279, -119.761, 147.911, 73.3968, 3.65598, 74.2541, 19.778, -2.2315, -111.056, -25.0304,
-86.2442, 0.146651, 83.5428, -29.3382, 64.0093, 147.03, 73.9582, 29.3652, 154.906, 6.25221, 112.96, 165.03, 11.5624, -48.3887, -130.92, 158.099,
-6.47314, -26.6561, -18.5458, -79.5949, 16.5753, 68.4287, 54.4969, 8.59587, -21.8077, -38.0325, -14.1827, -48.149, -7.71342, 5.32628, 34.3591, 4.97453,
-19.9588, -29.6581, -39.8474, 152.45, -7.02004, -71.166, 40.6025, 90.9133, 41.1172, 10.2277, -41.2978, -21.4705, -9.53513, 33.3237, -170.287, -147.144,
-21.8209, 27.7537, 19.2982, 29.7286, -13.7392, -55.8712, -28.3766, -8.00291, 125.209, 161.205, 19.9805, -46.2199, -2.73427, -12.1052, 106.535, 20.4942,
-28.1138, 4.59628, 62.9273, -0.534962, 6.33028, -7.44623, 29.7984, -42.8088, 5.32914, 17.9307, 174.593, -36.0277, 3.2934, 24.3011, 174.231, -1.94325,
107.108, -4.82491, 44.1005, -38.1958, 47.1931, 0.689977, -48.5599, -2.29967, -16.9223, -9.36993, -13.2723, 23.7414, 17.0389, 157.955, 52.6113,
14.0859, -100.053, -42.2958, -9.25703, 37.9416, 58.9846, -28.9415, -56.1025, 37.1207, 50.4847, -55.062

2EWH

151.436, -92.5903, -3.75076, -9.668, -0.975246, 10.9844, 84.1865, -57.1686, 38.7048, 72.7755, 64.7086, 50.2283, 29.5956, -111.649, 163.46, -92.508,
-148.929, 61.6607, 124.085, 171.298, -75.5506, -52.2331, -1.37142, -19.9511, 67.108, 14.27, -1.03143, 0.0222875, -116.144, -32.3217, -125.421,
-102.86, 145.85, 108.298, -60.4006, -54.4374, -88.1894, -14.6692, 121.958, 125.926, 167.02, -74.5737, -130.938, 62.1354, 106.58, 35.1401, 93.7873,
162.441, 14.5873, -4.93593, 6.27325, -7.31527, 10.8045, -53.8271, -132.021, -37.8517, 30.6805, -89.4307, -61.2859, -31.1104, 90.5217, 118.145,
-4.46292, -52.5412, 113.612, 159.141, -3.43442, 62.945, 12.7417, -19.7111, -15.1737, 30.368, -27.5934, -138.544, 7.81197, -59.2248, 9.7981, 122.127,
-164.755, 36.2949, 27.611, -37.779, 39.5707, -22.2883, 38.9922, 4.30684, 71.8969, -21.7556, -128.587, -76.5211, -0.480596, 65.3271, 8.48192, 158.34,
107.055, -66.142, 18.5806, -129.465, -18.4294, -11.7806, 50.9098, 132.39, 101.434, 0.100595, -28.2695, 0.622333, 52.5959, 150.715, -11.0556, -45.8273,
-39.1155, 8.30602, 56.8165, -46.0845, 17.9186, 11.1667, 19.5044, 89.7449, -23.746, -0.808862, 84.8186, 0.457484, -89.925, -21.9539, 26.9255, -59.9087,
45.3057, -9.74849, -70.462, -14.0544, 18.7807, 59.6121, -176.746, -30.6629, -54.0245, -8.68261, -14.3952, 43.302, 23.9289, 59.5115, -35.76, -58.2711,
2.27009, -152.857, -35.6967, -137.17, -49.407, 36.9083, 58.3246, -26.7135, -71.9911, 26.5305, 53.0114, 52.0147, -21.6699, -14.1031, 12.009, -63.6288,
-54.0997, -10.6967, 5.20745, -124.069, -19.2082, 55.6145, -3.07942, 12.0508, 131.359, -177.867, 32.7929, 24.0475, 25.0758, -0.0780254, 5.44473,
36.0356, 28.5948, 22.5261, -174.132, -3.91424, -11.5903, -132.095, -172.313, -25.055, -156.073, 11.1264, 29.3397, -64.3192, -38.8408, -177.009,
22.2676, 11.9142, 56.3727

F13

7.66522, -83.448, 13.0886, 0.55134, 29.1616, -47.908, 2.75327, -31.0327, -31.3119, -46.3918, 0.276218, 9.04884, -29.5745, -116.199, 160.508,
0.890189, 129.381, 24.5074, 113.38, -161.672, 98.7127

F13

7.66522, -83.448, 13.0886, 0.551338, 29.1616, -47.908, 2.75327, -31.0327, -31.3119, -46.3918, 0.276222, -9.04884, 29.5745, 116.199, -160.508,
-0.890189, -129.381, -24.5074, -113.38, 161.672, -98.7127

F21

-5.70817, -70.6345, 12.6013, -78.4561, 5.14012, 2.49148, 57.5974, -25.416, 27.2287, -35.8677, -5.33428, -13.9895, 3.02158, 19.9054, 74.4006, -31.0707,
4.76465, -19.1022, -32.9492, 155.506, -16.0013, -169.101, 162.893, -94.9124, 155.503, -140.891, 153.332, 40.6752, 137.563, 48.1957,
-35.2245, 66.7533, -37.5734, 137.909, -144.521, -52.7295, -156.871

F21

-5.70816, -70.6345, 12.6014, -78.4561, 5.14014, 2.49149, 57.5974, -25.416, 27.2287, -35.8677, -5.33427, -13.9895, 3.0216, 19.9055, 74.4006, -31.0707,
4.76466, -19.1022, -32.9492, -155.506, 16.0013, 169.101, -162.893, 94.9124, -155.503, 140.891, -153.332, -40.6752, -137.563, -48.1957,
35.2245, -66.7533, 37.5734, -137.909, 144.521, 52.7295, 156.871

F34

12.3298, -83.1718, 20.1532, 8.42606, 37.8998, -37.8448, 9.33408, -77.8143, 7.4245, -73.1774, 26.15, -80.0668, 46.3843, 6.49943, -29.8816, 51.2622,
-33.6564, 38.6885, -67.9543, 46.7986, -10.4886, -27.9647, -10.0583, -39.8364, -49.6972, -25.641, 44.7456, -59.6061, 18.6305, -20.9127, 25.4877,
13.4228, 1.77009, 42.1284, 129.207, -149.941, 1.89517, -120.166, 18.4003, 159.01, -168.548, 143.358, 151.62, -49.9323, -164.471, -44.6816, 177.501,
-32.6178, 2.86468, -2.00479, -22.1516, -57.0231, -143.09, 131.37, -127.956, 147.157, 57.657, -21.2642, 27.2822, -52.9505, 17.7835, 119.254, 18.7327

F55

-15.6437, 97.9193, 1.00666, 95.3815, 1.86855, -64.0331, -141.452, -2.83476, 104.146, 8.21281, -162.93, -74.3953, 1.96392, 7.65968, -29.2495, 52.5953,
52.8264, -0.624594, 137.07, -4.89079, 0.957561, 150.771, 19.388, 7.34186, 59.4269, 8.22775, -64.6383, -54.8633, -8.8461, 59.752, 162.033, 13.6066,
-78.2664, 13.0242, 102.375, 3.23899, -2.60196, -16.3626, 36.9652, -37.8734, 30.0569, 3.86882, -34.6667, -22.5344, 25.3408, 89.0776, 16.5037, -17.6911,
-91.108, 4.84917, -9.27247, -4.88184, 6.63221, 4.31554, -28.558, -8.46761, 171.776, -66.1542, 29.7446, -114.307, -0.574113, 83.8969, -5.34284, 64.1091,
6.16523, 112.965, -5.20239, 68.6776, -17.6844, -113.527, 31.5684, -100.963, 152.521, -49.1181, -26.2181, -129.399, -24.1061, 42.4841, -45.0845,
67.3054, -35.1296, 15.741, 34.8919, 33.4461, 7.88754, 179.833, 41.9367, -135.639, 118.444, -156.824, -55.2589, 169.967, 0.172651, 91.1955, -4.02574,
-81.307, 23.9152, -29.0528, -154.072, -133.971, 16.3457, -93.6495, -5.71876, 80.2119, -21.5927

F89

179.886, -95.54, -17.2583, -27.4664, -23.3,38.1298, 19.5766, 34.4132, 8.84695, -117.344, -20.5596, -131.943, -11.8962, -48.6976, 129.133, -107.932,
7.29644, 89.0642, 21.8161, 56.2631, -33.6006, -22.3247, -47.5945, -48.8527, -51.6802, 36.4829, 85.1461, 3.54137, 107.149, -0.955333, -51.2341,
65.8004, 13.8676, -69.7918, -0.860014, -134.319, -37.8356, -2.74527, -12.5366, -93.6285, -28.5384, -105.157, 19.0699, 81.6706, 6.93831, 0.887398,
116.484, 23.1153, 132.738, 10.4558, 73.2237, -15.4114, 6.88586, -109.859, -3.3155, -82.7065, 2.76043, -42.4804, 82.5479, -18.3209, -29.9615, -74.7318,
-24.0277, 60.1736, -26.3071, -15.531, -14.9412, -79.5093, -1.99245, -48.5295, -70.5006, 58.6443, -42.9465, 50.0326, -70.0616, -9.55698, -109.482,
-2.75044, -87.6997, -8.8569, 86.5537, -22.4479, 72.1052, 14.0501, -27.4652, -8.8744, 56.3962, 0.863411, -142.989, -54.5377, 29.0611, -61.1795, 50.3774,
-12.8387, 73.4752, 12.0947, -39.6898, -28.42, 143.035, 28.1471, 39.6651, 10.0519, -140.34, -2.35037, 123.344, 3.62448, 125.741, 132.141, 71.1956,
-36.3432, -36.7204, -39.5973, 57.8245, -31.8281, 13.6268, -143.946, -36.4178, -6.53297, 34.1645, 12.4669, -82.0619, 14.2377, -32.9623, 49.1945,
137.212, -16.0272, -178.526, 12.3581,69.7334, -1.88293, 147.327, 145.168, 27.4845, -35.3688, 8.48146, -81.2594, -5.25881, 119.388, -139.654, 57.454,
159.88, 27.509, -0.616009, 114.258, -13.2053, -39.494, 65.2585, -42.1881, 0.311959, -22.2436, -162.899, -54.8573, -20.7022, -14.7214, 128.993, 5.42026,
114.069, -21.3562, -46.7891, 18.6434, 15.3431, 121.287, -3.95967, -82.6683, -9.4711, -120.912, -1.33882, -28.956, 43.9338, -42.9642, -139.445, 137.938,
4.62324

18

Borko Bošković, Janez Brest

(a) 1BXP

(b) 1BXP

(c) 1CB3

(d) 1CB3

(e) 1BXL

(f) 1BXL

(g) 1EDP

(h) 1EDP

(i) 2ZNF

(j) 2ZNF

(k) 1EDN

(l) 1EDN

(m) 2H3S

(n) 2H3S

(o) F13

(p) F13

(q) F21
Fig. 7 The best obtained conformations that could be optimal.

(r) F21

Protein Folding Optimization using DE with Local Search and Component Reinitialization
12. Hsu, H.P., Mehra, V., Grassberger, P.: Structure optimization in an off-lattice protein model. Phys. Rev. E
68 (2003). doi:10.1103/PhysRevE.68.037703
13. Hsu, H.P., Mehra, V., Nadler, W., Grassberger, P.:
Growth algorithms for lattice heteropolymers at low temperatures. The Journal of Chemical Physics 118(1), 444–
451 (2003). doi:10.1063/1.1522710
14. Huang, W., Liu, J.: Structure optimization in a threedimensional off-lattice protein model.
Biopolymers
82(2), 93–98 (2006). doi:10.1002/bip.20400
15. Jana, N.D., Sil, J., Das, S.: An Improved Harmony Search
Algorithm for Protein Structure Prediction Using 3D OffLattice Model, pp. 304–314. Springer Singapore, Singapore (2017). doi:10.1007/978-981-10-3728-3 30
16. Jana, N.D., Sil, J., Das, S.: Selection of appropriate metaheuristic algorithms for protein structure prediction in
{AB} off-lattice model: a perspective from fitness landscape analysis. Information Sciences 391392, 28–64
(2017). doi:10.1016/j.ins.2017.01.020
17. Kennedy, D., Norman, C.: Editorial: So much
more to know.
Science 309, 78–102 (2005).
doi:10.1126/science.309.5731.78b
18. Kim, J., Straub, J.E., Keyes, T.: Structure optimization
and folding mechanisms of off-lattice protein models using statistical temperature molecular dynamics simulation: Statistical temperature annealing. Phys. Rev. E 76
(2007). doi:10.1103/PhysRevE.76.011913
19. Kim, S.Y.: Three-dimensional off-lattice ab model protein with the 89-residue fibonacci sequence. Chaos,
Solitons & Fractals 90(Supplement C), 111–117 (2016).
doi:10.1016/j.chaos.2016.04.010
20. Kim, S.Y., Lee, S.B., Lee, J.: Structure optimization by conformational space annealing in an offlattice protein model.
Phys. Rev. E 72 (2005).
doi:10.1103/PhysRevE.72.011916
21. Lau, K.F., Dill, K.A.: A lattice statistical mechanics
model of the conformational and sequence spaces of
proteins. Macromolecules 22(10), 3986–3997 (1989).
doi:10.1021/ma00200a030
22. Li, B., Chiong, R., Lin, M.: A balance-evolution artificial bee colony algorithm for protein structure optimization based on a three-dimensional AB off-lattice model.
Computational Biology and Chemistry 54, 1–12 (2015).
doi:10.1016/j.compbiolchem.2014.11.004
23. Li, B., Lin, M., Liu, Q., Li, Y., Zhou, C.: Protein folding
optimization based on 3D off-lattice model via an improved artificial bee colony algorithm. Journal of Molecular Modeling 21(10), 261 (2015). doi:10.1007/s00894015-2806-y
24. Li, Y., Zhou, C., Zheng, X.: The Application of Artificial Bee Colony Algorithm in Protein Structure Prediction. In: L. Pan, G. Pun, M. Prez-Jimnez, T. Song
(eds.) Bio-Inspired Computing - Theories and Applications, Communications in Computer and Information
Science, vol. 472, pp. 255–258. Springer Berlin Heidelberg (2014). doi:10.1007/978-3-662-45049-9 42
25. Márquez-Chamorroa,
A.E.,
Asencio-Cortésa,
G.,
Santiesteban-Tocab, C.E., Aguilar-Ruiza, J.S.: Soft
Computing Methods for the Prediction of Protein
Tertiary Structures: A Survey. Applied Soft Computing
35, 398–410 (2015). doi:10.1016/j.asoc.2015.06.024
26. Mount, D.W.: Bioinformatics: Sequence and Genome
Analysis. New York: Cold Spring Harbor Laboratory
Press (2001)
27. Petsko, G., Ringe, D.: Protein Structure and Function.
Primers in biology. New Science Press (2004)

19

28. PJ, T., BH, Q., PL, P.: Defective protein folding as a
basis of human disease 20, 456–459 (1995)
29. Selkoe, D.J.: Folding proteins in fatal ways. Nature pp.
900–904 (2003). doi:10.1038/nature02264
30. Stillinger, F.H., Head-Gordon, T.: Collective aspects of
protein folding illustrated by a toy model. Phys. Rev. E
52, 2872–2877 (1995). doi:10.1103/PhysRevE.52.2872
31. Stillinger, F.H., Head-Gordon, T., Hirshfeld, C.L.: Toy
model for protein folding. Phys. Rev. E 48, 1469–1477
(1993). doi:10.1103/PhysRevE.48.1469
32. Storn, R., Price, K.: Differential Evolution - a simple
and efficient adaptive scheme for global optimization over
continuous spaces. Tech. Rep. TR-95-012, Berkeley, CA
(1995)
33. Storn, R., Price, K.: Differential Evolution - A Simple and
Efficient Heuristic for Global Optimization Over Continuous Spaces. J. Glob. Optim. 11(4), 341–359 (1997)
34. Thachuk, C., Shmygelska, A., Hoos, H.H.: A replica
exchange monte carlo algorithm for protein folding in
the hp model. BMC Bioinformatics 8(1), 342 (2007).
doi:10.1186/1471-2105-8-342
35. Wang, T., Zhang, X.: 3D Protein Structure Prediction
with Genetic Tabu Search Algorithm in Off-Lattice AB
Model. In: Knowledge Acquisition and Modeling, 2009.
KAM ’09. Second International Symposium on, vol. 1,
pp. 43–46 (2009). doi:10.1109/KAM.2009.2
36. Wang, T., Zhang, X.: A case study of 3D protein structure prediction with genetic algorithm and Tabu search.
Wuhan University Journal of Natural Sciences 16(2),
125–129 (2011). doi:10.1007/s11859-011-0723-1
37. Wang, Y., Guo, G., Chen, L.: Chaotic Artificial Bee
Colony algorithm: A new approach to the problem of minimization of energy of the 3D protein
structure. Molecular Biology 47(6), 894–900 (2013).
doi:10.1134/S0026893313060162
38. Wong, K.C., Wu, C.H., Mok, R.K.P., Peng, C., Zhang,
Z.: Evolutionary multimodal optimization using the
principle of locality. Inf. Sci. 194, 138–170 (2012).
doi:10.1016/j.ins.2011.12.016
39. Zhang, X., Cheng, W.: Protein 3D Structure Prediction by Improved Tabu Search in Off-Lattice AB Model.
In: Bioinformatics and Biomedical Engineering, 2008.
ICBBE 2008. The 2nd International Conference on, pp.
184–187 (2008). doi:10.1109/ICBBE.2008.50
40. Zhang, X., Wang, T., Luo, H., Yang, J.Y., Deng, Y.,
Tang, J., Yang, M.Q.: 3D Protein structure prediction
with genetic tabu search algorithm. BMC Systems Biology 4, 1–9 (2010). doi:10.1186/1752-0509-4-S1-S6
41. Zhou, C., Hou, C., Wei, X., Zhang, Q.: Improved hybrid
optimization algorithm for 3D protein structure prediction. Journal of Molecular Modeling 20(7), 2289 (2014).
doi:10.1007/s00894-014-2289-2
42. Zhou, C., Hu, T., Zhou, S.: Protein Structure Prediction Based on Improved Multiple Populations and GAPSO. In: L. Pan, G. Pun, M. Prez-Jimnez, T. Song
(eds.) Bio-Inspired Computing - Theories and Applications, Communications in Computer and Information
Science, vol. 472, pp. 644–647. Springer Berlin Heidelberg (2014). doi:10.1007/978-3-662-45049-9 105

