Solving the protein threading problem in parallel

We propose a network flow formulation for protein threading and show its equivalence with the shortest path problem on a graph with a very particular structure. The underlying mixed integer programming (MIP) model proves to be very appropriate for the protein threading problem - huge real-life instances have been solved in a reasonable time by using only a mixed integer optimizer instead of a special-purpose branch and bound algorithm. The properties of the MIP model allow decomposition of the main problem on a large number of subproblems (tasks). We show in this paper that a branch and bound-like algorithm can be efficiently applied to solving in parallel these tasks, which leads to a significant reduction in the total running time. Computational experiments with huge problem instances are presented.