We propose a network flow formulation for protein threading and show its equivalence with the shortest path problem on a graph with a particular structure. The underlying Mixed Integer Programming (MIP) model proves to be very appropriate-huge real-life instances have been solved in a reasonable time by using only a Mixed Integer Optimizer. The properties of the MIP model allow decomposition of the main problem on a large number of subproblems (tasks). We show that a branch&bound alike algorithm can be efficiently applied to solving in parallel these tasks, which leads to a significant reduction in the total running time.