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

(such as the reformulated variables) and introduce the products of the
original variables by new variables in order to derive higher dimen-
sional lower bounding linear programming (LP) relaxations for the
original problem [58]. These LP relaxations are solved during the
course of the overall branch and bound algorithm, and thus speed con-
vergence to the global minimum. The following set of constraints
illustrates the application of the RLT approach to the original composi-
tion constraint. First, the equations are reformulated by forming the
product of the equation with some binary variables or their comple-
ment. For example, by multiplying by the set of variables

y l , the

following additional set of constraints ∀ j , k , l is produced:

m

j

i

yyy

l

=

l

∀ i k l ,,

∑

(14)

i

j = 1

This equation can now be linearized using the same variable substitu-
tion as introduced for the objective. The set of RLT constraints then
become:

m

jl

i
∑

l

wy = ∀ i k l ,,

(15)

ik k

j 1

Finally, for such an ILP problem it is straightforward to identify a rank-
ordered list of the low-lying energy sequences through the introduction
of integer cuts [56], and repetitive solution of the ILP problem. By using
the enhancements outlined above, in combination with the commercial
(LP) solver CPLEX [57], a globally optimal (ILP) solution is generated.

Fold Specificity
Once a set of low-lying energy sequences have been identified via the
sequence selection procedure, the fold stability and specificity valida-
tion stage is used to identify the most optimal sequences according to
a rigorous quantification of conformational probabilities. The approach
is based on the development of conformational ensembles for the
selected sequences under two sets of conditions. In the first circumstance
the structure is constrained to vary, with some imposed fluctuations,
around the template structure. In the second condition, a free folding
calculation is performed for which only a limited number of restraints
are likely to be incorporated (in the case of compstatin and its analogs,
only the disulfide bridge constraint is enforced) and with the underlying
template structure not being enforced. In terms of practical considera-
tions, the distance constraints introduced for the template-constrained
simulation can be based on the structural boundaries defined by the
NMR ensemble (in the case of compstatin and its analogs a deviation
of 1.5 Å is allowed for each nonconsecutive C a -C a distance from the