Reconstruction of 3D Structures From Protein Contact Maps

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: Heinz Breu , David G. Kirkpatrick, Unit disk graph recognition is NP-hard, Computational Geometry: Theory and Applications, v.9 n.1-2, p.3-24, Jan. 1998 [doi>10.1016/S0925-7721(97)00014-X]
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 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: Arthur M. Lesk, Introduction to Bioinformatics, Oxford University Press, 2002
• 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: Jorge J. Moré , Zhijun Wu, Distance Geometry Optimization for Protein Structures, Journal of Global Optimization, v.15 n.3, p.219-234, October 1999 [doi>10.1023/A:1008380219900]
• 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.
• 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.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Pattern analysis
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design

Keywords:
Combinatorial algorithms, Contact map, Molecular Modeling, Protein structure prediction