article

Reconstruction of 3D Structures From Protein Contact Maps

Authors:

Luciano Margara,

Pietro Di Lena,

Piero Fariselli,

Rita CasadioAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 3

Pages 357 - 367

https://doi.org/10.1109/TCBB.2008.27

Published: 01 July 2008 Publication History

Abstract

The prediction of the protein tertiary structure from solely its residue sequence (the so called Protein Folding Problem) is one of the most challenging problems in Structural Bioinformatics. We focus on the protein residue contact map. When this map is assigned it is possible to reconstruct the 3D structure of the protein backbone. The general problem of recovering a set of 3D coordinates consistent with some given contact map is known as a unit-disk-graph realization problem and it has been recently proven to be NP-Hard. In this paper we describe a heuristic method (COMAR) that is able to reconstruct with an unprecedented rate (3-15 seconds) a 3D model that exactly matches the target contact map of a protein. Working with a non-redundant set of 1760 proteins, we find that the scoring efficiency of finding a 3D model very close to the protein native structure depends on the threshold value adopted to compute the protein residue contact map. Contact maps whose threshold values range from 10 to 18 Ångstroms allow reconstructing 3D models that are very similar to the proteins native structure.

References

[1]

S.F. Altschul, T.L. Madden, A.A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D.-J. Lipman, "Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs," Nucleic Acids Research, vol. 25, no. 17, pp. 3389-3402, Sept. 1997.

[2]

D. Andreeva, S.E. Howorth, T.J. Brenner, C. Hubbard, and A.G. Chothia, "SCOP Database in 2004: Refinements Integrate Structure and Sequence Family Data," Nucleic Acids Research, database issue, vol. 32, pp. D226-D229, Jan. 2004.

[3]

L. Bartoli, E. Capriotti, P. Fariselli, P.L. Martelli, and R. Casadio, "The Pros and Cons of Predicting Protein Contact Maps, in Protein Structure Prediction," Methods and Protocols Humana Press, in press.

[4]

L.M. Blumental, Theory and Applications of Distance Geometry. Chelsea House Publishers, 1970.

[5]

J. Bohr et al., "Protein Structures from Distance Inequalities," J. Molecular Biology, vol. 231, pp. 861-869, 1993.

[6]

H. Breu and D.G. Kirkpatrick, "Unit Disk Graph Recognition Is NP-Hard," Computational Geometry, vol. 9, pp. 3-24, 1998.

Digital Library

[7]

T. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, second ed. MIT Press, McGraw-Hill, 2001.

Digital Library

[8]

G.M. Crippen and T.F. Havel, Distance Geometry and Molecular Conformation. John Wiley & Sons, 1988.

[9]

P. Fariselli, O. Olmea, A. Valencia, and R. Casadio, "Progress in Predicting Inter-Residue Contacts of Proteins with Neural Networks and Correlated Mutations," Proteins, vol. 45, Suppl 5. pp. 157-162, 2001.

[10]

S.G. Galaktionov and G.R. Marshall, "Properties of Intraglobular Contacts in Proteins: An Approach to Prediction of Tertiary Structure," System Sciences, Proc. 27th Hawaii Int'l Conf. Biotechnology Computing, vol. 5, nos. 4-7, pp. 326-335, Jan. 1994.

[11]

B.L. de Groot, D.M.F. van Aalten, R.M. Scheek, A. Amadei, G. Vriend, and H.J.C. Berendsen, "Prediction of Protein Conformational Freedom from Distance Constraints," Proteins, vol. 29, pp. 240-251, 1997.

[12]

T.F. Havel, Distance Geometry: Theory, Algorithms, and Chemical Applications in the Encyclopedia of Computational Chemistry, 1998.

[13]

D.A. Hinds and M.A. Levitt, Proc. Nat'l Academy of Sciences of the USA, vol. 89, p. 2536, 1992.

[14]

A. Lesk, Introduction to Bioinformatics. Oxford Univ. Press, 2006.

Digital Library

[15]

J. Moré and Z. Wu, "{Epsilon}-Optimal Solutions to Distance Geometry Problems via Global Continuation," Global Minimization of Non-Convex Energy Functions: Molecular Conformation and Protein Folding, P. M. Pardalos, D. Shalloway, and G. Xue, eds., pp. 151- 168, Am. Math. Soc., 1995.

[16]

J. Moré and Z. Wu, "Distance Geometry Optimization for Protein Structures," J. Global Optimization, vol. 15, pp. 219-234, 1999.

Digital Library

[17]

G. Pollastri, A. Vullo, P. Frasconi, and P. Baldi, "Modular DAGRNN Architectures for Assembling Coarse Protein Structures," J. Computational Biology, vol. 13, no. 3, pp. 631-650, 2006.

[18]

J.B. Saxe, "Embeddability of Weighted Graphs in K-Space Is Strongly NP-Hard," Proc. 17th Allerton Conf. Comm. Control, and Computing, pp. 480-489, 1979.

[19]

M. Vassura, L. Margara, P. Di Lena, F. Medri, P. Fariselli, and R. Casadio, "Reconstruction of 3D Structures from Protein Contact Maps," Proc. Third Int'l Symp. Bioinformatics Research and Applications (ISBRA '07), pp. 578-589, 2007.

Digital Library

[20]

M. Vendruscolo, E. Kussell, and E. Domany, "Recovery of Protein Structure from Contact Maps," Folding and Design, vol. 2, no. 5, pp. 295-306, Sept. 1997.

[21]

M. Vendruscolo and E. Domany, "Protein Folding Using Contact Maps," Vitamins and Hormones, vol. 58, pp. 171-212, 2000.

Cited By

Yu DLi YHu JYang XYang JShen H(2015)Disulfide connectivity prediction based on modelled protein 3D structural information and random forest regressionIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2014.235945112:3(611-621)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TCBB.2014.2359451
Di Lena PFariselli PMargara LVassura MCasadio R(2011)Is There an Optimal Substitution Matrix for Contact Prediction with Correlated Mutations?IEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2010.918:4(1017-1028)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TCBB.2010.91
Sergienko IRyazanov VBiletskyy BByts AGupal ARzhepeskyy S(2010)Methods to predict protein spatial structureCybernetics and Systems Analysis10.1007/s10559-010-9181-646:1(34-50)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/s10559-010-9181-6
Show More Cited By

Index Terms

Reconstruction of 3D Structures From Protein Contact Maps

Recommendations

An evolutionary approach for protein contact map prediction
EvoBIO'11: Proceedings of the 9th European conference on Evolutionary computation, machine learning and data mining in bioinformatics

In this study, we present a residue-residue contact prediction approach based on evolutionary computation. Some amino acid properties are employed according to their importance in the folding process: hydrophobicity, polarity, charge and residue size. ...
Evolutionary protein contact maps prediction based on amino acid properties
HAIS'11: Proceedings of the 6th international conference on Hybrid artificial intelligent systems - Volume Part II

Protein structure prediction is one of the main challenges in Bioinformatics. An useful representation for protein 3D structure is the protein contact map. In this work, we propose an evolutionary approach for contact map prediction based on amino acids ...
Evolutionary decision rules for predicting protein contact maps

Protein structure prediction is currently one of the main open challenges in Bioinformatics. The protein contact map is an useful, and commonly used, representation for protein 3D structure and represents binary proximities (contact or non-contact) ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 5, Issue 3

July 2008

159 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 2008

Published in TCBB Volume 5, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu DLi YHu JYang XYang JShen H(2015)Disulfide connectivity prediction based on modelled protein 3D structural information and random forest regressionIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2014.235945112:3(611-621)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TCBB.2014.2359451
Di Lena PFariselli PMargara LVassura MCasadio R(2011)Is There an Optimal Substitution Matrix for Contact Prediction with Correlated Mutations?IEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2010.918:4(1017-1028)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TCBB.2010.91
Sergienko IRyazanov VBiletskyy BByts AGupal ARzhepeskyy S(2010)Methods to predict protein spatial structureCybernetics and Systems Analysis10.1007/s10559-010-9181-646:1(34-50)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/s10559-010-9181-6
Di Lena PFariselli PMargara LVassura MCasadio R(2009)On the upper bound of the prediction accuracy of residue contacts in proteins with correlated mutationsProceedings of the 9th international conference on Algorithms in bioinformatics10.5555/1812906.1812912(62-72)Online publication date: 12-Sep-2009
https://dl.acm.org/doi/10.5555/1812906.1812912
Piovesan DDi Lena PVassura MFariselli PMartelli PVassura MDi Lena P(2009)Unconventional training for neural network predictions of inter-residue contactsProceedings of the 1st ACM workshop on Breaking frontiers of computational biology10.1145/1531780.1531785(19-26)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.1145/1531780.1531785

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents