  This paper presents efficient algorithms for solving the problem of aligning
a protein structure template to a query amino-acid sequence, known as protein
threading problem. We consider the problem as a special case of graph matching
problem. We give formal graph and integer programming models of the problem.
After studying the properties of these models, we propose two kinds of
Lagrangian relaxation for solving them. We present experimental results on real
life instances showing the efficiency of our approaches.
