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

18.3.8 Experimental Comparison of the MIP Models

Extensive computational experiments in [28, 29] showed that MXYZ significantly
outperforms the LS algorithm and the MXZ model. Here we present results from [30]
which compare the models MXYZ , MYZ , and RAPTOR . The models were solved
using CPLEX 7.1 on a Pentium 2.40 GHz Linux PC with 4 GB of RAM. The models
are compared on real-life instances generated by Fold Recognition Oriented Search
Tool (FROST) software [27].
The most important observation is that for almost all (about 95%) the instances, the
LP relaxation of all three models is integer-valued, thus providing optimal threading.
This is true even for polytopes with more than 10 46 vertices. Table 18.1 shows the
number of simplex iterations and the time for each model on a sample from these
instances. More precisely, of the 3600 instances solved by the MYZ model, the LP
solution is noninteger in only 182 cases (about 5%). In all these cases, the solution
contains mainly zeros and ones, and several 0.5 values. The largest number of nodes
in the B&B tree for the 182 noninteger instances is 11; only 17 instances have a tree
with six or more nodes (these instances are shown in Table 18.2). In most instances,
only two nodes are sufficient for attaining optimality. The behavior of the other two
models is similar. The number of nodes is slightly different from one model to another,
and from CPLEX 7.1 to 8.0, but always stays in the same range of values. Table 18.2
shows that most of the solution time is usually spent in solving the LP relaxation.
In addition, the gap between the LP score and the MIP score is so small that the LP
relaxation could very well predict the closest template when comparing a query to
multiple templates. There are, in fact, many similarities with the classic uncapacitated
plant-location problem, in which most of the instances are easy to solve [38, 39]. The
good behavior of the LP relaxation is definitely lost when using randomly generated

TABLE 18.1 A Set of Instances where the LP Solution is Integer

MXYZ RAPTOR MYZ

Query Space

Length Size Iter. Time Iter. Time Iter. Time

491 2.9E21 13624 25 13864 26 7907 13

491 2.5E25 22878 83 25747 118 10566 29

522 1.8E26 20627 111 15723 94 7920 22

491 1.1E27 41234 276 47082 347 16094 58

455 1.5E29 30828 390 36150 596 25046 241

522 1.8E29 18949 161 18598 169 12307 77

491 1.1E30 28968 365 40616 604 13870 68

491 1.4E30 58602 1303 66816 2083 29221 401

491 3.2E30 34074 572 41646 659 22516 186

522 5.3E31 26778 334 33395 468 13752 64

294 4.1E38 43694 619 52312 749 36539 314

583 1.3E39 124321 6084 147828 8019 57912 1120

757 9.9E45 121048 4761 166067 7902 92834 3117

Note : Times are in seconds. For all instances, the MYZ model provides the best time.