Protein Threading: From Mathematical Models to Parallel Implementations

This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These models allow for an efficient decomposition and for the application of a parallel branch-and-cut algorithm, significantly reducing the running time. The efficiency of our approach has been confirmed by extensive computational experiments.