Comparing graph representations of protein structure for mining family-specific residue-based packing motifs.
We find recurring amino-acid residue packing patterns, or spatial motifs, that are characteristic of protein structural families, by applying a novel frequent subgraph mining algorithm to graph representations of protein three-dimensional structure. Graph nodes represent amino acids, and edges are chosen in one of three ways: first, using a threshold for contact distance between residues; second, using Delaunay tessellation; and third, using the recently developed almost-Delaunay edges. For a set of graphs representing a protein family from the Structural Classification of Proteins (SCOP) database, subgraph mining typically identifies several hundred common subgraphs corresponding to spatial motifs that are frequently found in proteins in the family but rarely found outside of it. We find that some of the large motifs map onto known functional regions in two protein families explored in this study, i.e., serine proteases and kinases. We find that graphs based on almost-Delaunay edges significantly reduce the number of edges in the graph representation and hence present computational advantage, yet the patterns extracted from such graphs have a biological interpretation approximately equivalent to that of those extracted from distance based graphs.
Huan
Jun
J
Department of Computer Science, University of North Carolina, 3239 Sitterson Hall, Chapel Hill, NC 27599, USA.
Bandyopadhyay
Deepak
D
Wang
Wei
W
Snoeyink
Jack
J
Prins
Jan
J
Tropsha
Alexander
A
D000465:Algorithms; D020816:Amino Acid Motifs; D019295:Computational Biology; D003196:Computer Graphics; D030562:Databases, Protein; D008958:Models, Molecular; D015233:Models, Statistical; D015394:Molecular Structure; D011506:Proteins / Q000737:chemistry* / Q000145:classification*; D040681:Structural Homology, Protein
D011506:Proteins