{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:39:42Z","timestamp":1760243982679,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2009,1,22]],"date-time":"2009-01-22T00:00:00Z","timestamp":1232582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a2010076","type":"journal-article","created":{"date-parts":[[2009,1,22]],"date-time":"2009-01-22T10:30:48Z","timestamp":1232620248000},"page":"76-92","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Reconstruction of Three-dimensional Protein Structures from Contact Maps"],"prefix":"10.3390","volume":"2","author":[{"given":"Pietro","family":"Di Lena","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Bologna, Via Mura Anteo Zamboni, 7, 40127 Bologna, Italy"}]},{"given":"Marco","family":"Vassura","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Bologna, Via Mura Anteo Zamboni, 7, 40127 Bologna, Italy"}]},{"given":"Luciano","family":"Margara","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Bologna, Via Mura Anteo Zamboni, 7, 40127 Bologna, Italy"}]},{"given":"Piero","family":"Fariselli","sequence":"additional","affiliation":[{"name":"Biocomputing Group, Department of Biology, University of Bologna, Via Irnerio, 42, 40127 Bologna, Italy"}]},{"given":"Rita","family":"Casadio","sequence":"additional","affiliation":[{"name":"Biocomputing Group, Department of Biology, University of Bologna, Via Irnerio, 42, 40127 Bologna, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2009,1,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1126\/science.181.4096.223","article-title":"Principles that govern the folding of protein chains","volume":"181","author":"Anfinsen","year":"1973","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1098\/rstb.2005.1803","article-title":"Prediction and design of macromolecular structures and interactions","volume":"361","author":"Baker","year":"2006","journal-title":"Phil. Trans. R. Soc. London B Biol. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zaki, M.J., and Bystroff, C. (2008). Protein Structure Prediction, Humana Press.","DOI":"10.1007\/978-1-59745-574-9"},{"key":"ref_4","first-page":"1","article-title":"LETTERS AND COMMENTS: The effect of backbone on the small-world properties of protein contact maps","volume":"1","author":"Bartoli","year":"2007","journal-title":"Physical Biology"},{"key":"ref_5","unstructured":"Blumental, L.M. (1953). Theory and applications of distance geometry, Clarendon Press."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","article-title":"Unit disk graph recognition is NP-hard","volume":"9","author":"Breu","year":"1998","journal-title":"Computational Geometry"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1006\/jmbi.1993.1332","article-title":"Protein structures from distance inequalities","volume":"231","author":"Bohr","year":"1993","journal-title":"J. Molecular Biology"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1002\/prot.21637","article-title":"Assessment of intramolecular contact predictions for CASP7","volume":"69","author":"Izarzugaza","year":"2007","journal-title":"Proteins"},{"key":"ref_9","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001). Introduction to Algorithms, McGraw-Hill Book Co.. [2nd ed.]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1093\/protein\/14.11.835","article-title":"Prediction of contact maps with neural networks and correlated mutations","volume":"14","author":"Fariselli","year":"2001","journal-title":"Protein Engineering"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1093\/bib\/bbl032","article-title":"The WWWH of remote homolog detection: The state of the art","volume":"8","author":"Fariselli","year":"2007","journal-title":"Briefings in Bioinformatics"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Galaktionov, S.G., and Marshall, G.R. (,  1994). Properties of intraglobular contacts in proteins: An approach to prediction of tertiary structure. Proceedings of the 27th Hawaii International Conference on System Sciences, IEEE Society Press, USA.","DOI":"10.1109\/HICSS.1994.323564"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_14","unstructured":"Crippen, G.M., and Havel, T.F. (1988). Distance geometry and molecular conformation, Research Studies Press Ltd."},{"key":"ref_15","unstructured":"Ragu\u00e9, V., Schreiner, P.R., Allinger, N.L., Clark, T., Gasteiger, J., Kollman, P.A., and Schaefer, H.F. (1998). Encyclopedia of Computational Chemistry, J. Wiley & Sons."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Pardalos, P. M., Shalloway, D., and Xue, G. (1995). Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding, American Mathematical Society.","DOI":"10.1090\/dimacs\/023"},{"key":"ref_17","unstructured":"Kuhn, F., Moscibroda, T., and Wattenhofer, R. (, January October). Unit disk graph approximation. Proceedings of 2nd ACM Joint Workshop on Foundations of Mobile Computing, Philadelphia, Pennsylvania, USA."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bandyopadhyay, S., Maulik, U., and Wang, J. T. L. (2007). Analysis of Biological Data: A Soft Computing Approach, World Scientific.","DOI":"10.1142\/9789812708892"},{"key":"ref_19","unstructured":"Saxe, J. B. (,  1979). Embeddability of weighted graphs in k-space is strongly NP-hard. Proceedings of the 17th Allerton Conference on Communications, Control, and Computing."},{"key":"ref_20","unstructured":"Snyman, J.A. (2005). Practical mathematical optimization: an introduction to basic optimization theory and classical and new gradient-based algorithms, Springer-Verlag."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1109\/TCBB.2008.27","article-title":"Reconstruction of 3D Structures From Protein Contact Maps","volume":"5","author":"Vassura","year":"2008","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1093\/bioinformatics\/btn115","article-title":"FT-COMAR: fault tolerant three-dimensional structure reconstruction from protein contact maps","volume":"24","author":"Vassura","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_23","first-page":"25","article-title":"Fault Tolerance for Large Scale Protein 3D Reconstruction from Contact Maps","volume":"4645","author":"Vassura","year":"2007","journal-title":"Springer Verlag Lecture Notes in Bioinformatics"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S1359-0278(97)00041-2","article-title":"Recovery of protein structure from contact maps","volume":"2","author":"Vendruscolo","year":"1997","journal-title":"Folding and Design"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/1\/76\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:09:44Z","timestamp":1760220584000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/1\/76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,22]]},"references-count":24,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2009,3]]}},"alternative-id":["a2010076"],"URL":"https:\/\/doi.org\/10.3390\/a2010076","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,1,22]]}}}