Biology Reference
In-Depth Information
the energy according to the parameters that multiply the binary vari-
ables, can be expressed as:
m
m
n
n
jl
j
i
k
min
Ex
(
,
xxyy
k
)
l
∑
∑
∑
∑
i
ik
i
yy
j
l
i
=
1
j
=
1
ki
=+
1
l
=
1
i
k
subject to
m
j
i
y
=
1
∀
i
∑
i
j
=
1
j
l
yy
,
=−
01
∀
ijkl
, ,
,
i
k
jl
The parameters depend on the distance between the alpha-
carbons at the two backbone positions (
x
i
,
x
k
) as well as the type of
amino acids at those positions. The composition constraints require
that there is exactly one type of amino acid at each position. For the
general case, the binary variables appear as bilinear combinations in
the objective function. Fortunately, this objective can be reformulated
as a strictly linear (integer linear programming) problem [56]:
Exx
ik
(, )
i
k
m
m
n
n
jl
jl
i
k
min
Ex
(
,
xxw
k
)
∑
∑
∑
∑
i
ik
ik
yy
j
l
i
=
1
j
=
1
ki
=+
1
l
=
1
i
k
subject to
m
j
i
y
=
1
∀
i
∑
i
subjec to
j
=
1
j
j
l
j
l
yy
+−≤
1
w
≤
y
∀
i j k l
,, ,
,,
i
i
k
ik
jl
l
0
≤≤
wy
∀
i j k
,
l
ik
k
j
l
yy
,
=−
01
∀
ijkl
, ,
,
i
This reformulation relies on the transformation of the bilinear combina-
tions to a new set of linear variables,
w
jl
ik
, while the addition of the four sets
of constraints serves to reproduce the characteristics of the original formu-
lation. For example, for a given
i
,
j
,
k
,
l
combination, the four constraints
require
w
i
jl
j
y
l
to be 0 when either
y
i
or
is equal (or when both are equal
to 0). If both
y
j
i
and
y
k
are equal to 1, then
w
jl
ik
is also enforced to be 1.
The solution of the integer linear programming problem (ILP) can be
accomplished rigorously using branch and bound techniques [56,57]
making convergence to the global minimum energy sequence consis-
tent and reliable. Furthermore, the performance of the branch and
bound algorithm is significantly enhanced through the introduction of
reformulation linearization techniques (RLT). The basic strategy is to
multiply appropriate constraints by bounded nonnegative factors
Search WWH ::
Custom Search