Comparing graph-based representations of protein for mining purposes

ABSTRACT

Recently, the principles of graph theory are being adopted to address molecular and chemical structures investigations such as 3D protein structure prediction and spatial motifs discovery. Proteins have been parsed into graphs according to several approaches and methods and then studied based on graph theory concepts and data mining tools. In this paper we make a brief survey on the most used graph-based representations and we propose a naïve method to help with the protein graph making since a key step of a valuable protein structure mining process is to build concise and correct graphs holding reliable information. We, also, show that some existing and widespread methods present remarkable weaknesses and don't really reflect the real protein conformation.

REFERENCES

• 1: Berman H. M., Westbrook J., Feng Z., Gilliland G., Bhat T. N., Weissig H., Shindyalov I. N.&Bourne P. E. (2000). The Protein Data Bank. Nucleic Acids Res, 28 (1): 235--242.
• 2: Kleywegt G. J. (1999). Recognition of spatial motifs in protein structures. J. Mol. Biol. 285, 1187--1197
• 3: Doppelt O., MoriaudF., Bornot A.,&de Brevern A. G. (2007). Functional annotation strategy for protein structures. Bioinformation, 1(9): 357--359.
• 4: Saidi R., Maddouri M.&Mephu Nguifo E. (2007) Biological Sequences Encoding for Supervised Classification. Intl. conf. on BioInformatics Research and Development (BIRD), TU Berlin, March 12--14, SpringerVerlag, LNBI 4414, 224--238.
• 5: Vishveshwara S., Brinda K. V.,&Kannan N. (2002). Protein structure: Insights from graph theory. J. Theor. Comp. Chem. 1(1): 187--211.
• 6: Brandon C.&Tooze J. (1991). Introduction to Protein Structure. Garland Publishing, New York/London.
• 7: Steudel R. (2003). Properties of Sulfur-Sulfur Bonds. Angewandte Chemie International Edition in English, 14 (10): 655--664.
• 8: Bondi A. (1964). Van der Waals Volumes and Radii. J. Phys. Chem, 68 (3): 441--451.
• 9: Brinda K. V.&Vishveshwara S. (2005). A Network Representation of Protein Structures: Implications for Protein Stability. Biophysical Journal, 89: 4159--4170.
• 10: Lovell S. C., Davis I. W., Arendall W. B., de Bakker P. I. W., Word J. M., Prisant M. G., Richardson J. S.&Richardson, D. C. (2003). Structure validation by Cαα geometry: φ, ψ and Cβ deviation. Proteins Struct. Funct. and Genet. 50: 437--450.
• 11: Huan J., Bandyopadhyay D., Wang W., Snoeyink J., Prins J.&Tropsha A. (2005). Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs. Journal of Computational Biology, 12 (6): 657--671.
• 12: Jacobs D. J., Rader A. J., Kuhn L. A., and Thorpe M. F. (2001). Protein Flexibility Predictions Using Graph Theory. Proteins: Structure, Function, and Genetics 44: 150--165.
• 13: Keating K. S., Flores S. C., Gerstein M. B.,&Kuhn L. A. (2008) StoneHinge: Hinge Prediction by Network Analysis of Individual Protein Structures. Protein Science, 18 (2): 359--371.
• 14: Nikhil S. Ketkar , Lawrence B. Holder , Diane J. Cook, Subdue: compression-based frequent pattern discovery in graph data, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.71-76, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133915]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Reliability, Verification

Keywords:
amino acids, bonds, chemical interactions, discriminative feature, edges, graph representation, preprocessing, protein structure, vertices