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

where ν js is the number of variables of subproblem s , split on the j th segment. The
choice of the number of subproblems q is not obvious and will be discussed later.
The order in which the subproblems are solved is very important to the efficiency
of this approach. A better record v ∗ allows earlier cuts in the subproblems that follow.
Statistically, the chance of finding the global optimum in a subproblem is proportional
to the size of its search space. It is not difficult to see that the number of S - T paths

passing through a vertex (i , k) is i + k − 2
i i . From this, it is easy to compute

the search space size of each subproblem and to sort the subproblems in decreasing
order according to their size.
This splitting technique can be generalized for two (or more) segments. Consider
two segments i and j (Fig. 18.6 b ). As before, the possible positions for each segment
are partitioned into q subintervals, yielding q(q

m + n − i − k
m

− 1 −

1 )/ 2 subproblems. Segments i
and j can be chosen to minimize the maximal number of variables in the resulting
subproblems, and the subproblems can be solved in decreasing order on their search
space size. In the following paragraphs, SPLIT1 and SPLIT2 denote partitioning based
on one and two segments. Finding the best splitting segment(s) in SPLIT1 requires
considering each of the m segments, while in SPLIT2 m(m

+

1 )/ 2 pairs of segments
must be enumerated. In both cases, the time needed to choose the splitting segments
is negligible with respect to the time needed to solve the resulting subproblems.
Andonov et al. [30] have tested these splitting techniques on a large set of thread-
ing instances. Table 18.3 presents the running times for SPLIT1 and SPLIT2 on a
representative subset of these instances. The experiment shows that:

−

Splitting reduces the running time by a factor of more than 2 for bigger instances
when an appropriate number of subproblems are chosen.

•

Running time decreases up to certain number of subproblems, and then begins to
increase again. The best number of subproblems is relatively small (no more than
15 for all solved instances). This phenomenon is due not only to the increased

•

( a ) ( b )

k

i

Figure 18.6 Instance with five segments and six free positions. ( a ) The problem is split on
segment 3 into three subproblems. The feasible set of the second subproblem is defined by
L 2 = ( 1, 1, 3, 3, 3 ) and U 2 = ( 4, 4, 4, 6, 6 ) .( b ) The problem is split on segments 2 and 4 into

six subproblems. The feasible set of the second subproblem is defined by L 2

= ( 1, 1, 1, 3, 3 )

and U 2 = ( 2, 2, 4, 4, 6 ) .