Use of techniques derived from graph theory to compare secondary structure motifs in proteins

Abstract

A substructure matching algorithm is described that can be used for the automatic identification of secondary structural motifs in three-dimensional protein structures from the Protein Data Bank. The proteins and motifs are stored for searching as labelled graphs, with the nodes of a graph corresponding to linear representations of helices and strands and the edges to the inter-line angles and distances. A modification of Ullman's subgraph isomorphism algorithm is described that can be used to search these graph representations. Tests with patterns from the protein structure literature demonstrate both the efficiency and the effectiveness of the search procedure, which has been implemented in FORTRAN 77 on a MicroVAX-II system, coupled to the molecular fitting program FRODO on an Evans and Sutherland PS300 graphics system.