A graph-theoretic approach to the identification of three-dimensional patterns of amino acid side-chains in protein structures.

This paper discusses the use of graph-theoretic methods for the representation and searching of three-dimensional patterns of side-chains in protein structures. The position of a side-chain is represented by pseudo-atoms, and the relative positions of pairs of side-chains by the distances between them. This description of the geometry can be represented by a labelled graph in which the nodes and the edges of the graph represent the pseudo-atoms and the sets of inter-pseudo-atomic distances, respectively. Given such a representation, a protein can be searched for the presence of a user-defined query pattern of side-chains by means of a subgraph-isomorphism algorithm which is implemented in the program ASSAM. Experiments with one such algorithm, that due to Ullmann, show that it provides both an effective and a highly efficient way of searching for patterns of side-chains. The method is illustrated by searches for the serine protease catalytic triad, for residues involved in the catalytic activity of staphyloccocal nuclease, and for the zinc-binding side-chains of thermolysin. The catalytic triad pattern search revealed the existence of a second Asp-His-Ser triad-like arrangement of residues in trypsinogen and chymotrypsinogen, in addition to the catalytic residues. In addition the program can be used to search for hypothetical patterns, as is shown for a pattern of three tryptophan side-chains. These searches demonstrate that the search algorithm can successfully retrieve the great majority of the expected proteins, as well as other, previously unreported proteins that contain the pattern of interest.

Structural similarity between binding sites in influenza sialidase and isocitrate dehydrogenase: implications for an alternative approach to rational drug design.

Using searching techniques based on algorithms derived from graph theory, we have established a similarity between a 3-dimensional cluster of side chains implicated in drug binding in influenza sialidase and side chains involved in isocitrate binding in Escherichia coli isocitrate dehydrogenase. The possible implications of the use of such comparative methods in drug design are discussed.

Three-dimensional structural resemblance between the ribonuclease H and connection domains of HIV reverse transcriptase and the ATPase fold revealed using graph theoretical techniques.

Using 3D searching techniques based on algorithms derived from graph theory, we have established two previously unreported structural similarities involving the ribonuclease H (RNase H) domain of HIV-1 reverse transcriptase (RT). First, we report that there is a strong similarity between the 3D folds of the RNase H domain of RT and the 'ATPase folds' of hexokinase, the 70 kDa heat-shock cognate protein and actin. Like RNase H, these enzymes are involved in nucleotide binding and metal ion-catalysed cleavage of a phosphodiester bond. Similarities of the folding motif and the position of the metal-binding site in these enzymes suggest possible functional analogies and evolutionary relationships with RNase H. Second, we find there is a strong resemblance between the folds of the RNase H domain and of the p66 and p51 'connection' domains of RT. It is possible that this striking similarity within the RT structure indicates a possible ancestral gene doubling event. The similarity may also indicate that the connection domains possess functional roles in addition to those previously suggested, and they may therefore represent a further target for the design of therapeutic agents.

Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm.

A program called PROTEP is described that permits the rapid comparison of pairs of three-dimensional protein structures to identify the patterns of secondary structure elements that they have in common. The representation of the protein structures as labelled graphs, where the secondary structure elements in a protein and the spatial and angular relationships between them correspond to the nodes and edges of a graph, was developed for use with an earlier program, called POSSUM, which identified subgraph isomorphisms in protein structures. PROTEP takes this representation and uses a different and more flexible approach to locating structural patterns in pairs of proteins, using a maximal common subgraph isomorphism algorithm that is based on a clique detection procedure. A range of searches is described to demonstrate that areas of common structural overlap between protein structures taken from the Protein Data Bank can be identified both effectively and efficiently.

Similarity searching in databases of three-dimensional molecules and macromolecules.

This paper discusses algorithmic techniques for measuring the degree of similarity between pairs of three-dimensional (3-D) chemical molecules represented by interatomic distance matrices. A comparison of four methods for the calculation of 3-D structural similarity suggests that the most effective one is a procedure that identifies pairs of atoms, one from each of the molecules that are being compared, that lie at the center of geometrically-related volumes of 3-D space. This atom mapping method enables the calculation of a wide range of types of intermolecular similarity coefficient, including measures that are based on physicochemical data. Massively-parallel implementations of the method are discussed, using the AMT Distributed Array Processor, that achieve a substantial increase in performance when compared with a sequential implementation on a UNIX workstation. Current work involves the use of angular information and the extension of the method to field-based similarity searching. Similarity searching in 3-D macromolecules is effected by the use of a maximal common subgraph (MCS) isomorphism algorithm with a novel, graph-based representation of the tertiary structures of proteins. This algorithm is being used to identify similarities between the 3-D structures of proteins in the Brookhaven Protein Data Bank; its use is exemplified by searches involving the NAD-binding fold motif.

Three-dimensional structural resemblance between leucine aminopeptidase and carboxypeptidase A revealed by graph-theoretical techniques.

Using 3-D searching techniques based on algorithms derived from graph theory we have established a striking structural similarity between the structure of bovine carboxypeptidase A and that of the C-terminal domain of bovine leucine aminopeptidase. There is no significant sequence homology between the aminopeptidases and the carboxypeptidases but the strong structural relationship detected in this complex fold suggests that there may be a very remote divergent evolutionary relationship between these two enzyme classes.