## 2 Protein contact maps  
There are several definitions of _residue-to-residue contacts_ in literature. The two most widely accepted ones are those which define two residues to be in contact when (in the protein native structure) the distance between their carbon-alpha (\(C_{\alpha}\)) or carbon-beta (\(C_{\beta}\)) atoms is below some given threshold. While there is some difference between \(C_{\alpha}\) and \(C_{\beta}\) contact maps, the representation adopted is not crucial for the algorithms we will present here and throughout the rest of the paper we will only consider \(C_{\alpha}\) contact maps. An important property of \(C_{\alpha}\) contacts is that the distance between the \(C_{\alpha}\) atoms of two consecutive residues is always an almost constant value close to \(3.8\)A. This is no more true if we consider \(C_{\beta}\) distances of consecutive residues. Given some protein \(P\) consisting of \(N\) residues we can describe its structure by means of a set of three-dimensional coordinates \(c_{i}=(x_{i},y_{i},z_{i}),1\leq i\leq N\) which correspond to the positions of the \(C_{\alpha}\) atoms of the protein residues. The _contact map_\(M\in\{0,1\}^{N\times N}\) of _threshold_\(t\) for protein \(P\) is a two-dimensional approximation of the protein structure and it is defined as  
\[M_{ij}=\left\{ \begin{array}{cc}1&if\ |c_{i}-c_{j}|\leq t\\ 0&if\ |c_{i}-c_{j}|>t\end{array} \right.\]  
where  
\[|c_{i}-c_{j}|=\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2}}\]  
is the Euclidean distance between coordinates \(c_{i}\) and \(c_{j}\). From now on we will keep the notation consistent in the rest of the paper and we will refer to the length of a protein with the symbol \(N\); with \(c_{i}\) we will refer to some \(i\)-th coordinate and we will use the symbols \(M\) and \(t\) to denote a contact map and its threshold, respectively. The threshold value determines the amount of information about the protein structure contained in a contact map. For low threshold values the number of contacts observed in a protein structure is relatively sparse if compared to the number of non-contacts. The typical threshold values adopted are \(7\)-\(8\)A. These threshold values are the ones which minimize the distance between residue physical contacts and \(C_{\alpha},C_{\beta}\) contacts (see, for example, [4]). The \(C_{\beta}\) representation with threshold \(8\)A is the definition of contact currently adopted to evaluate the performances of contact predictors in CASP experiments (see, for example, [8]). With these definitions of threshold, the number of contacts between residues which are distant in the protein primary sequence (long range contacts) is very small. This is an important point since long-range contacts are the most informative about protein structures and they are also the most difficult to predict. Increasing the threshold value usually implies better performances for the reconstructing algorithms but, on the contrary, this does not imply an increase in the accuracy of the contact predictions, which is currently very low. A reconstructing algorithm from a contact map \(M\) must be able to recover a set of coordinates which satisfies as much as possible the constraint imposed by \(M\). We say that a set of coordinates \(c_{1},..,c_{N}\) is consistent with \(M\) if \(\forall i,j,|c_{i}-c_{j}|\leq t\) if and only if \(M_{ij}=1\). Very likely a predicted contact map \(M\) is not _physical_ which implies that no set of consistent coordinates with \(M\) exist at all. The success of a reconstructing algorithm from contact maps is measured in terms of the number of contacts correctly recovered while a qualitative measure of the success of the algorithm is provided by the _root mean square deviation_ (RMSD) between the reconstructed three-dimensional structure and the native one. The RMSD measure is commonly used to compare two molecular structures described by some set of coordinates \(C=(c_{1},..,c_{N})\) and \(C^{\prime}=(c^{\prime}_{1},..,c^{\prime}_{N})\).