_Algorithms_**2009**, 2, 76-92; DOI: 10.3390/a2010076  
_Review_  
**On the Reconstruction of Three-dimensional Protein Structures from Contact Maps**  
**[PERSON] \({}^{1,\star}\), [PERSON] \({}^{1}\), [PERSON] \({}^{1}\), [PERSON] \({}^{2}\) and [PERSON] \({}^{2}\)**  
\({}^{1}\) Department of Computer Science, University of Bologna, [PERSON], 7, 40127 Bologna, Italy  
\({}^{2}\) Biocomputing Group, Department of Biology, University of Bologna, Via Irnerio, 42, 40127 Bologna, Italy  
E-mails: {dilena, vassura, [EMAIL_ADDRESS]; [EMAIL_ADDRESS]; [EMAIL_ADDRESS]  
\({}^{\star}\) Author to whom correspondence should be addressed. _Received: 30 November 2008; in revised form: 8 January 2009 / Accepted: 20 January 2009 / Published: 22 January 2009_  
**Abstract:** The problem of protein structure prediction is one of the long-standing goals of Computational Biology. Although we are still not able to provide first principle solutions, several shortcuts have been discovered to compute the protein three-dimensional structure when similar protein sequences are available (by means of comparative modeling and remote homology detection). Nonetheless, these approaches can assign structures only to a fraction of proteins in genomes and ab-initio methods are still needed. One relevant step of ab-initio prediction methods is the reconstruction of the protein structures starting from inter-protein residue contacts. In this paper we review the methods developed so far to accomplish the reconstruction task in order to highlight their differences and similarities. The different approaches are fully described and their reported performances, together with their computational complexity, are also discussed. **Keywords:** Protein folding; contact map; molecular modeling. Introduction  
Proteins are polymers of _amino acids_ (also referred to as _residues_). Every protein is uniquely identified by its one-dimensional (1D) sequence of amino acids (_primary structure_), which are covalently bonded together to create a continuous and non-overlapping chain called the _backbone_ of the protein. The [PERSON]'s dogma [1] states that, under the same environmental conditions, every protein _folds_ spontaneously into a characteristic three-dimensional (3D) structure (_tertiary structure_). Protein biological functions are strictly related to the folded state and several biological diseases are believed to be the consequence of misfolded proteins. The process by which proteins fold into their native states is still a matter of debate. At the coarsest level it seems that often the folding process involves first the establishment of regular _secondary structure_ elements, such as _alpha helices_ and _beta sheets_, and afterwards the establishment of the tertiary structure. The most important aspect is that protein primary sequences seem to contain all information needed to drive the fold to the native structures. One of the grand challenges in Bioinformatics is to understand the rules which drive the folding process by starting from only the residue sequence. Currently, protein structures are typically solved experimentally by time-consuming X-ray crystallography or NMR spectroscopy. In the last 25 years the amount of electronic information contained in the protein data bank repository (PDB*) has been growing enormously. The parallel increase of computational power motivated the development of computational approaches to the folding recognition problem, being building by _homology_ the most effective one. This method is based on the notion that proteins which share high sequence similarity fold into the same native structure (with few exceptions). Protein evolutionary process tends to preserve more the structure than the sequence and a target protein can be usually modeled with good accuracy on a related template protein (for which the fold is known) by performing a _sequence alignment_, i.e. by mapping residues of the target protein into residues of the template protein. The overall quality of the fold recognition depends on the quality of the alignment.