High-Performance Alignment Methods for Protein Threading - Parallel Computing for Bioinformatics and Computational Biology - page 434

from method to method. Here we give a general definition, compatible to most of the
threading methods. We only assume that the score function is additive and can be
computed considering interactions between at most two amino acids at a time. These
assumptions allow to represent the score function by two groups of coefficients:

c ik , i = 1, ... , m , k = 1, ... , n , the score for placing segment i on position k ;

•

c ikjl , (i , j) n , the score induced by the pairwise interaction

between segments i and j when segment i is on position k and segment j is on
position l .

∈ L ,1 ≤ k ≤ l ≤

•

The coefficients c ik are some function (usually sum) of the preferences of each query
amino acid placed in segment i for occupying its assigned position, as well as the scores
of pairwise interactions between amino acids belonging to segment i . The coefficients
c ikjl include the scores of interactions between pairs of amino acids belonging to
segments i and j . Loops may also have sequence-specific scores, included in the
coefficients c i , k , i + 1, l .
Alternatively, we can represent the score function only by the second set of coeffi-
cients. To do this, it is sufficient to add c ik to all coefficients c i , k , i + 1, l , l

k , ... , n .In
the subsequent sections we will use one of these representations, depending on which
one is more convenient.

=

Protein Threading Problem Using the earlier definitions, PTP is simply to find
the feasible threading of minimum score, or formally,

m

min c ir i + c ir i jr j | (r 1 , ... , r m ) ∈ T .

i = 1 (i , j) ∈ L

18.3 MIXED INTEGER PROGRAMMING MODELS

In this section we restate PTP as a network optimization problem. On the basis of this
reformulation, we present different mixed integer programming models for PTP in a
unified framework. At the end of the section we compare the efficiency of these models
by experimental results. Subsequently, we make a brief introduction to MIP and LP,
necessary to understand the rest of this section. The reader familiar with these topics
can skip directly to Section 18.3.1. For a more detailed and consistent introduction,
the reader is referred to any good integer programming textbook (e.g., [36]).
MIP deals with problems of optimizing (maximizing or minimizing) a linear
function of many variables subject to linear equality and inequality constraints and
integrality restrictions on some or all of the variables. Because of the robustness of
the general MIP model, a remarkably rich variety of optimization problems can be
represented by mixed integer programs. The general form of MIP is

min cx

,

R p Z n

z MIP = + dy | Ax + By ≤ b , x ∈ , y ∈

+ +