## 4 Approaches to the reconstruction problem from protein contact maps
### Methods based on simulated annealing
In the adaptation phase, coordinates are displaced at random by using crankshaft moves (which avoid the backbone to be broken). The displacement of coordinate \(c_{i}\) into \(c_{i}^{\prime}\) is accepted with probability  
\[\pi=\min\{1,e^{\frac{\Delta E_{a}}{T_{a}}}\}\]  
according to the standard Metropolis prescription. The term \(\Delta E_{a}=|E_{a}(c_{i})-E_{a}(c_{i}^{\prime})|\) is the change in the cost function induced by the move. The energy function of the adaption phase, defined by  
\[E_{a}(c_{i})=\sum_{k=1}^{N}K_{a}(M_{ik})\cdot\vartheta(t-|c_{i}-c_{k}|), \tag{7}\]  
apparently differs from the energy function of the growth phase only for the missing factor \((i-k)\) which means that in this phase long range contacts are not favored against short range contacts. Note that, also in this case, the energy function is computed only for the displaced coordinate since the move doesn't affect the rest of the structure. The temperature-like parameter \(T_{a}\) is not constant as in the previous phase but it is decreased slowly during the computation according to the number of missing contacts. Two regimes are identified. In the first one, the structure contains many missing contacts and it is very far from being consistent with the contact map. In the second regime, the structure contains few missing contacts and it is very close to be completely consistent with the contact map. The function \(K_{a}\) and the temperature-like parameter \(T_{a}\) are interpolated between these two limiting cases:  
\[K_{a}^{(n)}(M_{ij})=K^{f}(M_{ij})+[K^{s}(M_{ij})-K^{f}(M_{ij})]\cdot\sigma(n)\]  
and  
\[T_{a}^{(n)}=T_{a}^{f}+(T_{a}^{s}-T_{a}^{f})\cdot\sigma(n)\]  
where the function \[\sigma(n)=\frac{2}{1+e^{-an}}-1\]  
has the scope to interpolate between the two regimes (here \(n\) is the current number of iterations). The distance between the two regimes is obtained by opportune choices of \(K_{a}^{s},K_{a}^{f},T_{a}^{s},K_{a}^{f}\) and \(\alpha\). The authors describe another refinement stage after the adaption phase which fixes the chirality of the recovered structure. For more details refer to [24]. **[PERSON] et al. (2006)**  
This algorithm is currently used as the final step in the _Distill+_ architecture, a machine learning approach to ab initio protein structure prediction [18]. Distill resembles a set of machine learning predictors for 1D and 2D protein features and a 3D reconstructing algorithm which uses a simulated annealing procedure to recover the 3D structures from contact maps predicted in the previous stages. One notable difference with the other methods described here is that the Distill reconstructing algorithm takes into account some 1D constraints (for instance, whether some fragment should fold to alpha helices) which cannot be inferred directly from contact maps without having any knowledge about the protein primary sequences. This is an example of how more constraints can be added to the reconstruction problem in order to improve structure prediction. Footnote †: Freely available at _[[http://distill.ucd.ie/distill/_](http://distill.ucd.ie/distill/_)]([http://distill.ucd.ie/distill/_](http://distill.ucd.ie/distill/_)). Also in this case the reconstructing algorithm consists of a growth phase and an adaptation phase. The growing procedure is essentially the one described in the previous section except for one difference. If the fragment going from the \(i\)-th to the \(j\)-th residue of the chain is predicted as an alpha helix, then the coordinates from \(i\) to \(j\) are chosen in order to model an ideal alpha helix with random orientation. Also the adaptation procedure is similar to the one described in the previous section. The coordinates are displaced at random by using crankshaft moves. One difference from the previous method is that the secondary structure elements (helices) are displaced as a whole without modifying their shape. The main difference here consists in the way the energy function encodes the constraints on the whole structure.