Mathematical Modeling and Optimization Methods for De Novo Protein Design - Systems Biology: Networks, Models, and Applications - page 45

The Mayo group has pioneered the development of DEE and has
applied the method to design a variety of proteins [18,33-36].
Goldstein [37] improved the original DEE criterion by stating that
rotamer i r can be pruned if the energy contribution is always reduced
by an alternative rotamer i t :

N

Ei () − Ei () + ∑ min[(, ) Ei j − Ei j (, ] > 0

(11)

r t rs ts

s

ji ≠

For rotamer pair elimination, the corresponding inequality is [32]:

N

ε (, ) ij − ε ( , ) i j + ∑ min[(, , ) ε ijk − ε ((, , ] ijk

uv t

> 0 (12)

rs uv rs t

t

kij ≠ ,

In general, rotamer pair elimination is computationally more expensive
than single rotamer elimination, and methods have been developed by
Gordon and Mayo [38] to predict which doubles elimination inequali-
ties are the strongest.
Pierce et al. [31] introduced Split DEE which split the conformational
space into partitions and thus eliminated the dead-ending rotamers
more efficiently:

N

Ei () − Ei () + {min[(, ) Ei j − Ei j (, )]} + [ ( Ei k , ) − Ei k ( , )] > 0 (13)

∑

r t ru tu rv t v

u

jj k i , ≠≠

Further revisions and improvements on DEE had been performed by
Wernisch et al. [13] and Gordon et al. [39].
The protein design problem has been proved to be NP-hard [40],
which means that the time required to solve the problem varies expo-
nentially according to n m , where n is the average number of amino
acids to be considered per position and m is the number of residues.
Hence as the protein becomes big enough, deterministic methods may
reach a plateau, and this is when stochastic methods come into play.
Monte Carlo methods and genetic algorithms are the most commonly
used stochastic methods for de novo protein design. In Monte Carlo
methods, a mutation is performed at a certain position in the sequence,
the Boltzmann probability is calculated from the energies before and
after the mutation, and the temperature is compared to a random
number. The mutation is allowed if the Boltzmann probability is higher
than the random number, and rejected otherwise. Dantas et al.'s [41]
protein design computer program, RosettaDesign, applied Monte Carlo
optimization algorithms. In completely redesigning nine globular