## 4 Approaches to the reconstruction problem from protein contact maps
### Methods based on simulated annealing  
The _simulated annealing_ is a generic technique used to find an approximation of the global minimum of a given function when the search space is very large (see, for example, [13]). This technique is inspired from annealing in metallurgy where the microstructure of a material is altered by heating to a predetermined temperature and then cooling down to room temperature to improve ductility. By analogy with the physical process, at each step of the algorithm the current solution is replaced by a random nearby solution, chosen with a probability which depends on the current solution and on a global parameter \(T\), called _temperature_, that is gradually decreased during the computing process. The current solution changes almost randomly when \(T\) is large while the randomness decreases as \(T\) goes to zero. This prevents the method from becoming stuck at local minima, as it can happen with gradient descent methods. To our knowledge there are two methods that use a simulated annealing approach for the reconstruction problem. Both methods consist of two phases. A _growth_ phase, in which an almost random initial solution is built by adding step-by-step one coordinate at a time which satisfies local constraints. An _adaptation_ phase which uses simulated annealing to iteratively refine the initial solution. **[PERSON] et al. (1997)**  
This method has been described in [24]. The key ingredients are the definition adopted for the temperature-like parameter and the energy cost function used to evaluate the computed structure. During the growing phase one coordinate \(c_{i}\) at a time is added to the growing chain. Assume that the first \(c_{1},...,c_{i-1}\) coordinates have been chosen already. A number \(k\) (reported as \(10\)) of random direction vectors \(c^{(1)},...,c^{(k)}\) are generated obtaining a set of possible candidates for \(c_{i}\)  
\[c_{i}^{(j)}=c_{i-1}+c^{(j)}.\]  
The set of direction vectors \(c^{(j)}\) is randomly chosen from a uniform distribution. The set of distances \(|c_{i}^{(j)}-c_{i-1}|\) has average distribution \(3.8\) and small variance \(0.04\). Among the \(k\) possible candidates the best one is chosen to grow the chain. The best candidate is the one which maximizes the number of true positive contacts and minimizes the number of false positive contacts consistently with the contact map. In detail, every candidate \(c_{i}^{(j)}\) is scored according to the probability  
\[p^{(j)}=\frac{e^{\frac{E_{0}\left(c_{i}^{(j)}\right)}{T_{g}}}}{Z} \tag{5}\]  
where\[Z=\sum_{j=1}^{k}e^{-\frac{E_{g}\left(c_{i}^{(j)}\right)}{T_{g}}}\]  
is a normalization factor and \(T_{g}\) is a temperature-like parameter which is initialized to \(1\) in this phase. The energy cost function \(E_{g}\) (note that it is computed only with respect to the newly selected coordinate \(c_{i}^{(j)}\)) is defined by  
\[E_{g}\left(c_{i}^{(j)}\right)=\sum_{k=1}^{i-1}(i-k)\cdot K_{g}(M_{ik})\cdot \vartheta(t-|c_{i}^{(j)}-c_{k}|) \tag{6}\]  
where the factor \((i-k)\) is introduced to give more importance to long range contacts, \(\vartheta\) is the Heaviside step function and \(K_{g}(M_{ij})\) is a two-valued function defined by \(K_{g}(M_{ij})\leq 0\) if \(M_{ij}=1\) and \(K_{g}(M_{ij})\geq 0\) if \(M_{ij}=0\). This term has the effect to penalize false positive contacts and to reward true positive contacts. That is, when the distance \(|c_{i}^{(j)}-c_{k}|\) is below the contact map threshold \(t\) and \(M_{ij}=1\) then the candidate \(c_{i}^{(j)}\) is rewarded otherwise it is penalized. During the growth phase the values \(K_{g}(0)=0\) and \(K_{g}(1)=-1\) are chosen, i.e. false positive contacts are not penalized. Every chain grown in this way has a score defined by the product of the probabilities of its coordinates (i.e. the probabilities computed with equation (5)). The growth phase is computed several times from scratch (typically ten times) and the structure with the best score is selected as the starting point for the adaptation phase.