PROTEIN THREADING BASED ON NONLINEAR INTEGER PROGRAMMING
Wajeb Gharib Gharibi
Department of Computer Engineering & Networks
Jazan University
Jazan 82822-6694, Saudi Arabia
Gharibi@jazanu.edu.sa

Marwah Mohammed Bakri
Department of Biology
Jazan University
Jazan 755, Saudi Arabia
Marwah890@gmail.com

Abstract

PDB in the past three years have similar structural folds to
the ones in PDB.

Protein threading is a method of computational
protein structure prediction used for protein sequences
which have the same fold as proteins of known structures
but do not have homologous proteins with known
structure. The most popular algorithm is based on linear
integer programming.
In this paper, we consider methods based on
nonlinear integer programming. Actually, the existing
linear integer programming is directly linearized from the
original quadratic integer programming. We then develop
corresponding efficient algorithms.
Keywords: Protein Threading, Protein Structure
Alignment, Integer Programming, Relaxation

1

INTRODUCTION

Protein structure prediction from amino acid
sequence is a fundamental scientific problem and it is
regarded as a grand challenge in computational biology
and chemistry.
Protein threading problem also referred as the holy
grail of molecular biology on the second half of the
genetic code is to determine the three-dimensional folded
shape (protein structure prediction) of a protein (sequence
of characters drawn from an alphabet of 20 letters). It is
important because the biological function of proteins
underlies all life, their function is determined by their
three-dimensional shape, and their shape determined by
one-dimensional sequence.
The prediction is made by "threading" (i.e. placing,
aligning) each amino acid contained in the target
sequence to a position in the template structure, and
evaluating how well the target fits the template. After the
best-fit template is selected, the structural model of the
sequence is built based on the alignment with the chosen
template. The protein threading method is based on two
basic observations. One is that the number of different
folds in nature is fairly small (approximately 1000), and
the other is that according to the statistics of the Protein
Data Bank (PDB), 90% of the new structures submitted to

A general paradigm of protein threading consists of
the following four steps: the construction of a structure
template database, the design of the scoring function,
threading alignment and threading prediction. The third
step is one of the major tasks of all threading-based
structure prediction programs, which mainly dedicated to
solving the optimal alignment problem derived from a
scoring function considering pairwise contacts.
As a formal presentation of the problem, let C called
core be a set of m items , called segments of length .
This set must be aligned to a sequence L of N characters
from some finite alphabet. Let
be the position in L
where starts. An alignment is called feasible threading
if:
1)

for all i,

2) the length
characters; i.e

(called gap or loop) of uncovered
is bounded, say
.

Each feasible threading
) is scored
by a function
where score the
placement of the segment i to a given position and is
used in some experiments for scoring the gap between
two consecutive segments. If the problem now is to
minimize f(t) over the set F of feasible threading, one can
show the equivalents with the shortest path problem
between two vertices of a very structured graph.
The model of protein threading problem is to
minimize the objective function

Subject to

Where m is the number of segments,
(The number are the lengths of the segments increased
by
the minimal number of gaps between the
segments k and k+1) is the number of possible placements
of each segment relative to the end of the previous one,
are binary variables with
meaning the segment
i starts from the obuolute position
of the
position sequence L.
Many different algorithms have been proposed for
finding the correct threading of a sequence onto a
structure, though many make use of dynamic
programming in some form. For full 3-D threading, the
problem of identifying the best alignment is very difficult
(it is an NP-hard problem). Researchers have made use of
many combinatorial optimization methods to arrive at
solutions. There are many algorithms, for example, the
protein threading software RAPTOR, which is based on
linear integer programming.
In this paper, we focus on developing efficient
algorithms. We notice that the mathematical models used
in the literatures are normally a linear integer
programming, which can actually be regarded as a
linearization of a quadratic integer programming problem.
This motivates us to study the original quadratic integer
programming directly. Recently, quadratic integer
programming becomes a hot research topic in
optimization society. Many mathematical tools such as
conic programming are developed, with which we can
construct corresponding efficient algorithms.
Now, consider the zero-one quadratic programming
problem

P : min C T x  x T Qx
s.t. h x  x Gx  g
x  X  {0,1},
T

T

(1, 1)

smaller. More tight linearization strategies are proposed in
this article for further improvement.
This article is organized as follows. In section 2, we
shortly describe the existing efficient linearization
approach. In section 3, we introduce our approach and
represent the linearized model. We conclude the paper in
section 4.
2 THE EXISTING EFFICIENT LINEARIZATION
APPROACH
Define
i
 min
/ max  min / max{ Qi x : x  X }, i,

(2.1)

where Q i is the i-th row of Q, and X is any suitable
relaxation of X such that the problem (2.1) can be solved
relatively

easily.

 min / max be

i
components  min
,
/ max

the

vector

with

i  1, 2, ..., n, and

min/ max  diag ( i min/ max ) . Similarly, define
i
min
/ max  min / max{ Gi x : x  X }, i,

(2.2)

and
i
T
min / max  (min
/ max , i  1,..., n) ,
i
 min / max  diag (min
/ max , i  1,..., n).

Sherali and Smith [14] reformulated Problem P as
an equivalent bilinearly constrained bilinear problem by
introducing   Qx and  Gx . Linearizing the terms

x i  i and x i i by s i and z i respectively,

they

obtained

(1, 2)

BP : min cT x  eT S 
s. t. Qx  

(2,4)

(1, 3)

hT x  eT z  g

(2,5)

Gx  

(2,6)

where Q and G are general symmetric matrices of
dimension n  n .
This problem is a generalization of unconstrained
zero-one quadratic problems, zero-one quadratic knapsack
problems, quadratic assignment problems and so on. It is
clearly NP-hard.
Linearization strategies are to reformulate the zero-one
quadratic programs as equivalent mixed-integer
programming problems (1.1) and (1.3) with additional
binary variables and/or continuous variables and
continuous constraints, see [1, 2, 3, 6, 7, 8, 9, 10, 12, 13].
Recently, Sherali and Smith [14] developed small
linearizations for (1.1) - (1.3), which is more general with
structure. The linearization generated by our approach is

i
i
 min
xi  si'   max
xi , i

(2, 3)

(2,7)

imin xi  Si  imax xi (1  xi ), i,

(2,8)

imin xi  zi'  imax xi , i,

(2,9)

imin (1  xi )  (i  zi' )  imax (1  xi ), i,
x X
where e is a conformable vector of ones and the
constrains (2.7) - (2.10) comes from multiplying

(2, 10)
(2,11)

 min     max , min    max
by xi and (1  xi ).

(2.12)

let x be part of an optimal solution to Problem BP. Then x
solves Problem P.
Besides, BP can be improved by the additional cuts

BP (2.3) - (2.11) has the following equivalent compact
formulation
T
BP: min cT x  eT s   min
x

(2.13)

i
i
i
( min
  min
 wmax
) xi  si  zi  0, i,

(2.31)

which is derived from multiplying
i
max

i   i  w

i
max

by

 max{(G i  Qi )x : x  X } .

(2.14)

x i where w

T
hT x  eT z  min
xg

(2.15)

3

Gx  

(2.16)

i
i
0  si  ( max
  min
) xi , i,

(2.17)

Motivated by [15], we first reveal the relation between
general quadratic and piece-wise linear terms for zero-one
variables.

i
i
0  yi  ( max
  min
)(1  xi ), i,

(2.18)

Lemma 3.1. Let

s. t. Qx  y  s   min e

0  zi  (

i
max

  ) xi
i
min

  (i  zi )  
x X
i
min

i
max

(2.19)

 (

i
max

  ) xi , i, (2.20)
i
min

(2.21)

A REPRESENTATION APPROACH

i
i
i
xi Qi x  max{ min
xi , Qi x   max
xi   max
},

(3.1)

i
i
i
xi Qi x  min{ max
xi , Qi x   min
xi   min
}

(3.2)

via the linear transformation

Proof. Suppose

i
si  si   min
xi , i,

clearly

i
yi   i  si   min
(1  xi ), i,

zi  zi  

(2.22)

x , i,

i
min i

Since the optimization and constraint senses of BP
tend to push the variables s to their lower bounds and z to
their upper bounds, the final relaxed version of BP was
written as
T
BP: min cT x  eT s   min
x

(2.23)

x  X  {0,1}n . for all i  1,..., n ,

0

x i  0, the left hand side of (3.1) is

and

the

right

hand

i
side of (3.1) reads max{ max
, Qi x }  Qi x , which is
equal to the left hand side. The proof of (3.1) is completed
and (3.2) can be similarly verified.

Corollary 3.1.

Let x X  {0,1}n . for all i  1,..., n,
i
i
i
max{ min
xi , Qi x   max
xi   max
}  si 

0  y  [ max   min ](e  x)

(2.25)

 min{

s0

(2.26)
(2.27)

if and only if

Gx  z  min

(2.28)

si  xi Qi x.

0  z  [ max   min ] x

(2.29)

x X ,

(2.30)

T

T
min

by deleting the upper bounding inequalities for s and
  z in (2.17) and (2.20), and combining (2.16) with
(2.20).
It was shown in [14] that Problems BP and P are
equivalent in the sense that for each feasible solution to
one problem, there exists a feasible solution to the other
problem having the same objective value. Furthermore,

(3.3)

x , Qi x   x   },

i
max i

h xe z  x  g
T

becomes

x i  0, it must hold that x i  1, the right hand

(2.24)

s. t. Q x  y  s   min e

side

i
max{0, Qi x   max
}  0 . On the other hand, if

i
min i

i
min

(3.4)

Combining (3.1) with (3.2), we have
i
i
i
xi Qi x  max{ min
xi , Qi x   max
xi   max
}

 min{

x , Qi x  

i
max i

(3.5)

x   },

i
min i

i
min

The above results hold true for

G i and  ¸ defined

before. Linearization based on Corollary 3.1 is just BP
(2.3) - (2.11), where the linear inequalities (2.7) - (2.8) is
nothing but (3.3). We remark here the four inequalities
implied by (3.3) were first introduced in [8]. Actually, not

all inequalities (3,3) are necessary in the final linearized
model. To see this, below we first introduce the principle
of reformulating zero-one quadratic programs into piecewise linear programs. Generally, for continuous
programs, we have

n

hT x   zi  g ,

(3.9)

i 1

i
zi  max
xi ,

(3.10)

i
i
zi  Gi x  min
xi  min
,

(3.11)

Proposition 3.1. Any convex program with linear or
piece-wise linear objective function and constraints is
equivalent to a linear program in the sense that there is a
one-to-one projection between both feasible solutions.

since (3.9)-(3.11) is a relaxation of (3.7) and (3.9)-(3.11)
also implies (3.7).

Proof. We notice that min f ( x ) is equivalent to

Now we can obtain a linearization for (3.6)-(3.8),
which is similarly to BP except that we do not require
y  0 and z  0 . In other words, they are redundant in

min t
s.t. t  f ( x )  0

BP

Without loss of generality we assume that the
objective function is linear. The constraint set is convex
and characterized by piece-wise linear inequalities. It
follows that it is convex polyhedral, which must have
linear expression.
It is easy to see that the equivalence of Proposition
3.1 holds if we restrict the variables to be zeros or ones.
Next we show the existence of such equivalent 'convex'
piece-wise linear program for zero-one quadratic
minimization problem.
Proposition 3.2. For any zero-one quadratic minimization
problem, there is an equivalent zero-one piece-wise linear
program with convex objective function and constraints.
Proof. Clearly, the maximum of several linear
functions is convex and the minimum is concave. Then
(3.1) and (3.2) in Lemma 3.1 provide the convex and
concave formulations, respectively. Therefore, for any
given zero-one quadratic minimization problem, we can
obtain an equivalent convex piece-wise linear program by
using (3.1) and/or (3.2). Note that we use (3.1) and (3.2)
simultaneously only when handling equality constraints,
see also Corollary 3.1.
Now we can see that (1.1) - (1.3) has the following
equivalent formulation
n

i
i
i
min cT x   max{ min
xi , Qi x   max
xi   max
}

(3.6)

i 1

n

i
i
i
s.t. hT x   min {max
xi , Gi x  min
xi  min
}  g , (3.7)
i 1

x  X  {0,1}n .
Linearizing (3.6)-(3.8) becomes very easy. For
example, (3.7) is equivalent to

(3.8)

.

Finally, we point out that the non-necessity of
inequalities such as y  0 and z  0 was also observed
in [1, 2]. Actually, the linearization generated by our
convex piece-wise approach coincides theirs.

4

CONCLUSIONS

In this article, we defined the protein folding
problem and discussed its solution through presenting
small linearizations for the zero-one quadratic
minimization problem.
We present the equivalence of quadratic terms and
piece-wise linear terms for zero-one variables. There are
two piece-wise formulations, convex and concave cases.
We show the smaller linearization is based on the convex
piece-wise
objective
function
and
constraints.
Linearization generated by our approach is smaller than
that in [14]. Our approach can be easily extended to
linearize polynomial zero-one minimization problems
which have many applications, particularly in biological
computing problems.

5

REFERENCES

[1]. Adams W., and Forrester R., “A Simple Approach
for Generating Concise Linear Representations of
Mixed 0-1 Polynomial Programs,” Operations
Research Letters, vol. 33, no. 1, pp. 55-61, 2005.
[2]. Adams W., and Forrester R., “Linear Forms of
Nonlinear Expressions: New Insights on Old Ideas,”
Operations Research Letters, vol. 35, no. 4, pp. 510518, 2007.
[3]. Adams W., Forrester R., and Glover F.,
“Comparisons and Enhancement Strategies for
Linearizing Mixed 0-1 Quadratic Programs,”
Discrete Optimization, vol.1, no.2, pp. 99-120,
2004.

[4]. Adams W.P.,and Sherali H.D, “A tight linearization
and an algorithm for zero-one quadratic
programming problems,” Manage. Sci., vol.32, no.
10, pp. 1274-1290, 1986.
[5]. Al-Khayyal A. and Falk J.E., “Jointly constrained
biconvex
programming,”
Mathematics
of
Operations Research, vol.8, no. 2, pp. 273, 1983.
[6]. Chaovalitwongse W., Pardalos P. M. and Prokopyev
O.A., “A new linearization technique for multiquadratic 0-1 programming problems,” Operations
Research Letters, vol.32, pp.517-522, 2004.
[7]. Fortet R., “L'algebre de boole et ses applications en
recherche
operationnelle,”
Cahiers
du
Centred'Etudes de Recheche Operationnelle, vol.1,
pp. 5-36, 1959.
[8]. Glover F., “Imporved linear integer programming
formulations of nonlinear integer problems,”
Manage. Sci., vol. 22, no. 4, pp. 455-460, 1975.
[9]. Glover F. and Woolsey E., ”Further reduction of
zero-one polynomial programming problems to
zero-one linear programming problems,” Oper. Res.,
vol. 21, no. 1, pp. 156-161, 1973.
[10]. Glover F. and Woolsey E., “Converting the 0-1
polynomial programming problem to a 0-1 linear
program,” Oper. Res., vol.22, no. 1, pp.180-182,
1974.
[11]. McCormick P., ”Computability of global solution to
factorable nonconvex problems: Part I - Convex
underestimating
problems,”
Mathematical
Programming, vol.10, pp.147-175, 1976.
[12]. Oral M. and Kettani O., “A linearization procedure
for quadratic and cubic mixed-integer problems,”
Operations Research vol.40, pp.109-116, 1990.
[13]. Oral M. and Kettani O., “Reformulating nonlinear
combinatorial optimization problems for higher
computational efficiency,” European Journal of
Operational Research, vol.58, pp. 236-249, 1992.
[14]. Sherali H.D., Smith J.C., “An improved
linearization strategy for zero-one quadratic
programming problems,” Optimization Letters,
vol.1, pp. 33-47, 2007.
[15]. Xia Y., Yuan Y., “A new linearization method for
quadratic assignment problems,” Optimization
Methods and Software, vol. 21, no. 5, pp. 803-816,
2006.
[16]. Gharibi W., Xia Y., “A Tight Linearization Strategy
for Zero-One Quadratic Programming Problems”,
International Journal of Computer Science Issues
(IJCSI), Volume 9, Issue 3, April 2012.

