## 3 The papers
### Problem area # 3: protein structure  
Protein folding.The protein folding problem consists in computing the native fold of a protein from either its aminoacid sequence alone, or from the sequence and a library of known folds. The former case is called the _folding ab-initio_ problem, while the latter is called _threading_. In both cases, the optimal fold sought after should minimize the free energy of the structure. Unfortunately, there is no simple-to-handle formula for the free energy. One of the main questions studied today is that of approximating the protein energy by a suitable, simpler, function, such as a linear function whose contributions are some pairwise weights which depend on (the interaction forces between) pairs of aminoacids. This problem is studied, e.g., in
* [PERSON] et al. (2004) [OTH]  
where it is solved as an inverse optimization problem: starting from the optimal solutions (known protein folds, determined experimentally) try to infer a function which is optimized by these solutions and not by others. The problem is cast as a linear program. Since this is only an approximation, and it may happen that the LP is infeasible, the authors reduce the energy determination problem to a max feasible subsystem problem. Folding prediction ab-initio is a very difficult problem. A typical simplification, although still hard to solve, is to consider each aminoacid as one of two types: H, i.e, _hydrophobic_, or P, i.e., _hydrophilic_ (also called _polar_). A protein is then a string over \(\{H,P\}\). Furthermore, the folding angles are restricted to some set of discrete possibilities (e.g., 90 degrees only) and therefore the aminoacids have to be placed over the vertices of a 3D square lattice, following a so-called _self-avoiding_ walk. The objective function is that of placing in adjacent vertices of the lattice as many hydrophobic aminoacids as possible. This is called the HP model of protein folding. * [PERSON] et al. (2002); [ILP]  
propose integer linear programming approaches for the solution of the HP protein folding problem. It should be said that the ILP approach for this problem has not proved to be as effective as other solution methods. The ILP fails to find optimal folds for proteins longer than 30 aminoacids. The most successful approaches for HP folding are based on constraint programming, a technique that allows the optimal solution for instances of up to 200 aminoacids [42]. A much better success has been met by integer programming approaches for the protein threading problem. In particular, RAPTOR, a computer program implementing a Branch-and-Cut formulation for threading, has won the fully-automated fold prediction contest CAFASP. * [43]: [PERSON], [PERSON], [PERSON] and [PERSON] (2003) [ILP]
* [44]: [PERSON] and [PERSON] (2003) [ILP]
* [45]: [PERSON] and [PERSON] and [PERSON] (2004) [ILP]  
A parallelization of the ILP approach for protein threading has been studied in
* [46]: [PERSON] and [PERSON] and [PERSON] (2004) [OTH]  
Both an integer programming formulation and a Lagrangian-relaxation approach for threading are proposed in
* [47]: [PERSON], [PERSON], [PERSON] and [PERSON] (2005) [ILP,LR]  
Furthermore, threading has been successfully approached also by global, non-linear optimization algorithms. The approach described in
* [48]: [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON] and [PERSON] (2004) [OTH]  
was used to predict the fold of proteins of up to 4000 aminoacids. Protein design.In the _protein design_ problem, the objective is to determine a protein (i.e., an aminoacid sequence) that folds into a target structure. In a variant of the protein design problem, only part of the structure is fixed (the protein's _backbone_), while the rest of the structure, in the form of its _side-chains_), has to be chosen optimally from a library of side-chains conformations. * [49]: [PERSON] and [PERSON] and [PERSON] (2004) [OTH]
* [50]: [PERSON], [PERSON], [PERSON] (2005) [OTH]  
describe a quadratic optimization problem for protein design in the HP model.