IDENTIFICATION OF BETA-SHEET MOTIFS, OF PSI-LOOPS, AND OF PATTERNS OF AMINO-ACID-RESIDUES IN 3-DIMENSIONAL PROTEIN STRUCTURES USING A SUBGRAPH-ISOMORPHISM ALGORITHM

This paper discusses the use of graph-theoretical techniques for the representation and searching of 3-D protein structures that are represented by labeled graphs. Two types of graph are considered. The nodes in the first type of chemical graph describe the secondary-structure elements and the edges the geometric relationships between pairs of these elements. The use of Ullmann's subgraph isomorphism algorithm with these representations permits the identification of all occurrences of all possible beta-sheet motifs in a 114-protein subset of the Protein Data Bank. A binary notation is used to describe the parallel or antiparallel characters of adjacent strands in a sheet, and it is shown that very few of the possible types of sheet are found to occur in practice. Similar conclusions are obtained using a more detailed notation that includes the sheets' topological connectivities. The latter notation enables searches to be carried out for psi-loops and allows the identification of 20 proteins that had not previously been known to contain this type of loop. The nodes in the second type of protein graph describe the amino acid residues in protein structures and the edges the geometric relationships between pairs of these residues. The use of the Ullmann algorithm with these representations permits the identification of the occurrences of patterns of residues. The identification process is illustrated by means of searches for the two aspartate groups that are known to be involved in the catalytic mechanism of the aspartic proteinases.