## 4 Approaches to the reconstruction problem from protein contact maps
### Methods based on distance geometry and local search
#### [PERSON] et al. (2007)  
This algorithm++ has been developed recently [22, 23]. A first version of this algorithm which works only on native contact maps has been described in [21]. The algorithm is in three phases. In the first phase an initial set of coordinates is generated. The initial set of coordinates is iteratively refined in the second phase of the algorithm up to a final solution. The third phase fixes, if necessary, the backbone constraint. Footnote ‡: Freely available at _[[http://bioinformatics.cs.unibo.it/FT-COMAR_](http://bioinformatics.cs.unibo.it/FT-COMAR_)]([http://bioinformatics.cs.unibo.it/FT-COMAR_](http://bioinformatics.cs.unibo.it/FT-COMAR_)). In the first phase, the procedure tries to guess a possible initial solution. This first phase relies essentially on the Embed algorithm. In detail, the contact map is scanned to find independent subcomponents. Two disjoint fragments of the protein are independent if there are no medium-long range contacts between them. Once independent fragments (if any) are identified the algorithm tries to guess a possible 3D structure for any such component. A set of distances is guessed according to the following general scheme  
\[D_{ij}=\left\{ \begin{array}{ll}0&if\;\;i=j\\ 3.8&if\;\;|i-j|=1\\ 6\pm\epsilon&if\;\;|i-j|=2\;and\;M_{ij}=1\\ 7.5\pm\epsilon&if\;\;|i-j|=3\;and\;M_{ij}=1\\ t\pm\epsilon&if\;\;|i-j|\geq 4\;and\;M_{ij}=1\\ \infty&if\;\;M_{ij}=0\end{array} \right.\]  
where \(\epsilon\) is some small random error (in function of the threshold \(t\)). The missing distances (i.e. those initialized with \(\infty\)) are upper bounded by using the standard Shortest Paths algorithm (see, for example, [9]). The initial 3D structure of each component can be then recovered by using the Embed algorithm. The recovered structures are finally merged to obtain a unique initial solution. The merge procedure adds one component at a time by choosing a random orientation. For every component a number (reported as \(50\)) of random tries are done in order to choose the best possible orientation i.e. the orientation which minimizes the errors with respect to the contact map. In the second phase a correction/perturbation procedure is applied iteratively in order to refine the structure obtained in the first phase. The algorithm stops when either all constraints of the contact map are satisfied or when a control parameter \(\delta>0\) decreases to \(0\). The correction procedure tries to displace one coordinate at a time in order to satisfy more contact map constraints without introducing new errors. A coordinate \(c_{i}\) is _well placed_ if \(\forall j\in[1,N]\) if \(M_{ij}=1\) then \(|c_{i}-c_{j}|\leq t\) and if \(M_{ij}=0\) then \(|c_{i}-c_{j}|>t\). Every not well placed coordinate \(c_{i}\) is displaced by moving it on the surface of a sphere centered in \(c_{i}\) of radius (of mobility)  
\[r_{i}=\min\{D_{0}-t,t-D_{1}\} \tag{9}\]  
where  
\[D_{0}=\min\{|c_{i}-c_{j}|\;|\;M_{ij}=0\;\mbox{and}\;|c_{i}-c_{j}|>t\}\]and  
\[D_{1}=\min\{|c_{i}-c_{j}|\mid M_{ij}=1\ \text{and}\ |c_{i}-c_{j}|\leq t\}.\]  
Note that, by definition, every point in the surface of the sphere of radius \(r_{i}\) is _safe_ for \(c_{i}\) in the sense that it does not introduce new errors. A good position \(c_{i}^{\prime}\) for \(c_{i}\) can be approximated by  
\[c_{i}^{\prime}=\mathbf{F}\frac{r_{i}}{|\mathbf{F}|}\]  
where the pseudo-force \(\mathbf{F}\) is defined by  
\[\mathbf{F}=\sum_{j=0}^{N}sgn_{ij}\frac{c_{i}-c_{j}}{|c_{i}-c_{j}|} \tag{10}\]  
\[sgn_{ij}=\left\{ \begin{array}{ccc}-1&if&M_{ij}=1\\ +1&if&M_{ij}=0\end{array} \right.\]  
The perturbation procedure introduces small changes in the set of coordinates in the following way. For every couple of coordinates \(c_{i},c_{j}\) if \(t-\delta<|c_{i}-c_{j}|\leq t\) and \(M_{ij}=1\) then the coordinates \(c_{i},c_{j}\) are moved in order to be \(\delta/10\) closer. If \(t<|c_{i}-c_{j}|\leq t+\delta\) and \(M_{ij}=0\) then they are moved in order to be \(\delta/10\) more distant.