Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Finding recurring residue packing patterns, or spatial motifs, that characterize protein structural families is an important problem in bioinformatics. We apply a novel frequent subgraph mining algorithm to three graph representations of protein three-dimensional (3D) structure. In each protein graph, a vertex represents an amino acid. Vertex-residues are connected by edges using three approaches: first, based on simple distance threshold between contact residues; second using the Delaunay tessellation from computational geometry, and third using the recently developed almost-Delaunay tessellation approach.Applying a frequent subgraph mining algorithm to a set of graphs representing a protein family from the Structural Classification of Proteins (SCOP) database, we typically identify several hundred common subgraphs equivalent to common packing motifs found in the majority of proteins in the family. We also use the counts of motifs extracted from proteins in two different SCOP families as input variables in a binary classification experiment. The resulting models are capable of predicting the protein family association with the accuracy exceeding 90 percent. Our results indicate that graphs based on both almost-Delaunay and Delaunay tessellations are sparser than the contact distance graphs; yet they are robust and efficient for mining protein spatial motif.

REFERENCES

• 1: Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: nearest neighbor relations for imprecise points, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
• 3: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.51, December 09-12, 2002
• 4: Samarjit Chakraborty , Somenath Biswas, Approximation Algorithms for 3-D Commom Substructure Identification in Drug and Protein Molecules, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.253-264, August 11-14, 1999
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: L. Dehaspe, H. Toivonen, and R. D. King. Finding frequent substructures in chemical compounds. In 4th International Conference on Knowledge Discovery and Data Mining, pages 30--36, 1998.
• 7: B. Delaunay. Sur la sphère vide. A la memoire de Georges Voronoi. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk, 7:793--800, 1934.
• 8: P. W. Finn , L. E. Kavraki , J.-C. Latombe , R. Motwani , C. Shelton , S. Venkatasubramanian , A. Yao, RAPID: randomized pharmacophore identification for drug design, Proceedings of the thirteenth annual symposium on Computational geometry, p.324-333, June 04-06, 1997, Nice, France [doi>10.1145/262839.262993]
• 9: D. Fischer, H. Wolfson, S. L. Lin, and R. Nussinov. Three-dimensional, sequence order-independent structural comparison of a serine protease against the crystallographic database reveals active site similarities: potential implication to evolution and to protein folding. Protein Science, 3:769--778, 1994.
• 10: H. Grindley, P. Artymiuk, D. Rice, and P. Willet. Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol. biol., 229:707--721, 1993.
• 11: Matthias Höchsmann , Thomas Töller , Robert Giegerich , Stefan Kurtz, Local Similarity in RNA Secondary Structures, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.159, August 11-14, 2003
• 12: S. K. Hofmann, P. Bucher, L. Falquet, and A. Bairoch. The prosite database, its status in 1999. Nucleic Acids Res, 27(1):215--219, 1999.
• 13: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 14: J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraph in the presence of isomorphism. UNC computer science technical report TR03-021, 2003.
• 15: J. Huan, W. Wang, A. Washington, J. Prins, R. Shah, and A. Tropsha. Accurate classification of protein structural families based on coherent subgraph analysis. In Proc. Pacific Symposium on Biocomputing, 2004.
• 16: Piotr Indyk , Rajeev Motwani , Suresh Venkatasubramanian, Geometric matching under noise: combinatorial bounds and algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.457-465, January 17-19, 1999, Baltimore, Maryland, United States
• 17: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 18: D. Jacobs, A. Rader, L. Kuhn, and M. Thorpe. Graph theory predictions of protein flexibility. Proteins: Struct. Funct. Genet., 44:150--155, 2001.
• 19: Philip N. Klein, Computing the Edit-Distance between Unrooted Ordered Trees, Proceedings of the 6th Annual European Symposium on Algorithms, p.91-102, August 24-26, 1998
• 20: G. J. Kleywegt. Recognition of spatial motifs in protein structures. Journal of Molecular Biology, 285(4):1887--1897, 1999.
• 21: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 22: J. Liang, H. Edelsbrunner, P. Fu, P. Sudhakar, and S. Subramaniam. Analytical shape computing of macromolecules I: molecular area and volume through alpha shape. Proteins, 33:1--17, 1998.
• 23: A. Murzin, S. Brenner, T. Hubbard, and C. Chothia. Scop: a structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology, 247:536--40, 1995.
• 24: F. M. Richards. The interpretation of protein structures: total volume, group volume distributions, and packing density. J. Molecular Biology, 82:1--14, 1974.
• 25: B. Shapiro. An algorithm for comparing multiple RNA secondary structures. Comp. Appl. Biosci, 4(3):387--393, 1988.
• 26: R. Singh, A. Tropsha, and I. Vaisman. Delaunay tessellation of proteins. J. Comput. Biol., 3:213--222, 1996.
• 27: Tatsuya Akutsu , Hisao Tamaki , Takeshi Tokuyama, Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets, Proceedings of the thirteenth annual symposium on Computational geometry, p.314-323, June 04-06, 1997, Nice, France [doi>10.1145/262839.262989]
• 28: A. Tropsha, C. Carter, S. Cammer, and I. Vaisman. Simplicial neighborhood analysis of protein packing (SNAPP) : a computational geometry approach to studying proteins. Methods Enzymol., 374:509--544, 2003.
• 29: J. Tsai, R. Taylor, C. Chothia, and M. Gerstein. The packing density in proteins: Standard radii and volumes. Journal of Molecular Biology, 290(1):253--266, 1999.
• 30: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 31: S. Vishveshwara, K. V. Brinda, and N. Kannan. Protein structure: Insights from graph theory. J. of Theo. and Comp. Chem., 1(1):187--211, 2002.
• 32: H. Wako and T. Yamato. Novel method to detect a motif of local structures in different protein conformations. Protein Engineering, 11:981--990, 1998.
• 33: Jason T. L. Wang , Bruce A. Shapiro , Dennis Shasha , Kaizhong Zhang , Kathleen M. Currey, An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.8, p.889-895, August 1998 [doi>10.1109/34.709622]
• 34: L. Wernisch, M. Hunting, and S. Wodak. Identification of structural domains in proteins by a graph heuristic. Proteins, 35(3):338--352, 1999.
• 35: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 36: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]

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
          Subjects: Data mining

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
almost-delaunay, protein classification, subgraph mining