## 4 Approaches to the reconstruction problem from protein contact maps
### Methods based on the gradient minimization of a cost function  
The general idea of these methods is that starting from an initial set of coordinates the reconstruction problem can be formulated as the minimization of the squared deviation between the current set of distances and the expected distances. In detail, given a \(N\times N\) contact map \(M\) the reconstructing procedure tries to compute a set of coordinates which minimize some energy cost function of the form  
\[E=\sum_{i=1}^{N}\sum_{j=i}^{N}\left(\left|c_{i}-c_{j}\right|-d_{ij}\right)^{2} \tag{1}\]  
where, as usual, \(c_{i}\) is the Cartesian coordinate of the \(i\)-th residue, the real number \(\left|c_{i}-c_{j}\right|\) is the Euclidean distance between the \(i\)-th and the \(j\)-th coordinates and \(d_{ij}\) is the _expected_ distance between the \(i\)-th and \(j\)-th residues. The minimization of the energy function is carried out by standard gradient descent based methods (see, for example, [20]). A first difficulty with the minimization approach is that the expected distances are usually difficult to compute with high accuracy since a contact map contains only information about coarse lower and upper bounds. A second problem is that the cost function (1) does not embody the backbone constraint and the minimization procedure can eventually lead to a structure which has a broken backbone, i.e. the distances between two consecutive residues can be much larger than those in real proteins. In the sequel we review two methods which use this approach and which differ essentially on the way by which some constraints are added to equation (1) in order to solve the two problems described above. **[PERSON] et al. (1993)**  
The authors of [7] overcome the backbone and the expected distances problems by adding extra terms to the cost function (1) which becomes  
\[E=\sum_{i=1}^{N}\sum_{j=i}^{N}w_{ij}\cdot\left[S\left(\left|c_{i}-c_{j}\right| \right)-d_{ij}\right]^{2}+\sum_{i=1}^{N-1}E_{bond}^{i} \tag{2}\]  
The distance \(\left|c_{i}-c_{j}\right|\) is projected into the interval \([0,1]\) by the sigmoidal function  
\[S(x)=\frac{1}{1+e^{-a(x-i)}}\]  
where \(s\) is a slope constant (reported as \(1.5^{-1}\) A) which determines the steepness of the sigmoidal function in proximity of \(x=t\). The idea to project the current distances into the interval \([0,1]\) solves the problem to find a good approximation of the expected distances, thus the expected distance \(d_{ij}\) can be simply defined by  
\[d_{ij}=\left\{ \begin{array}{ll}0&if\ M_{ij}=1\\ 1&if\ M_{ij}=0\end{array} \right.\]avoiding any sort of approximation. A counter-effect of this approach is that the energy function has a local minimum when the distances diverge to infinity. This is a consequence of the fact that when a low threshold value \(t\) is chosen (recall that a typical value is around \(8\)A) the distances in real proteins below \(t\) are much more sparse compared to those above \(t\). This problem is solved by adding the weighting term  
\[w_{ij}=\left\{ \begin{array}{ll}\frac{N_{L}}{N_{L}+N_{S}}&if\ d_{ij}=0\\ \frac{N_{S}}{N_{L}+N}&if\ d_{ij}=1\end{array} \right.\]  
which has the effect to balance the weight of shorter distances with respect to larger distances (\(N_{L}\) and \(N_{S}\) are the number of distances above and below the threshold \(t\), respectively). The backbone constraint is introduced by adding the term \(\sum\limits_{i=1}^{N-1}E_{bond}^{i}\) with  
\[E_{bond}^{i}=\left\{ \begin{array}{ll}3.8-\epsilon-|c_{i}-c_{i+1}|&if\ |c_{i}-c_{i+1}|<3.8-\epsilon\\ 0&if\ 3.8-\epsilon<|c_{i}-c_{i+1}|<3.8+\epsilon\\ |c_{i}-c_{i+1}|-3.8-\epsilon&if\ |c_{i}-c_{i+1}|>3.8+\epsilon\end{array} \right.\]  
where the parameter \(\epsilon\) is a small quantity (reported as \(0.2\) A). The initial configuration is chosen at random in a cubic box of total volume \(100\)A\({}^{3}\). **[PERSON] and [PERSON] (1994)**  
The main difference between this method [12] and the previous one is in the approach adopted to deal with the approximation of the expected distances.