Comparison of protein surfaces using a genetic algorithm.

A genetic algorithm (GA) is described which is used to compare the solvent-accessible surfaces of two proteins or fragments of proteins, represented by a dot surface calculated using the Connolly algorithm. The GA is used to move one surface relative to the other to locate the most similar surface region between the two. The matching process is enhanced by the use of the surface normals and shape terms provided by the Connolly program and also by a simple hydrogen-bonding descriptor and an additional shape descriptor. The algorithm has been tested in applications ranging from the comparison of small surface patches to the comparison of whole protein surfaces, and it has performed correctly in all cases. Examples of the matches are given and a quantitative analysis of the quality of the matches is performed. A number of possible future enhancements to the program are described which would allow the GA to be used for more complex surface comparisons.

Biotin carboxylase comes into the fold.

Extensive three-dimensional structural resemblances between biotin carboxylase and the ADP-forming peptide synthetases, represented by glutathione synthetase and D-Ala:D-Ala ligase, reveal a previously unsuspected evolutionary relationship between two major families of ADP-forming ligases.

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.

Pharmacophoric pattern matching in files of three-dimensional chemical structures: characterization and use of generalized torsion angle screens.

This paper describes the use of generalized torsion angles for the screening of conformational searches in databases of three-dimensional chemical structures. A generalized torsion angle is defined as the dihedral angle between two vectors, A1-A2 and A3-A4, in which none, some, or all of the vectors A1-A2, A2-A3, and A3-A4 correspond to formal chemical bonds. The screens consist of a set of four atoms together with an associated angular range, and are identified by a statistical analysis of the frequencies of occurrence of these features in the Cambridge Structural Database. These frequencies are discussed, and the effectiveness of the screens is demonstrated by an extensive series of searches for representative pharmacophoric patterns.

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.

Pharmacophoric pattern matching in files of three-dimensional chemical structures: characterization and use of generalized valence angle screens.

This paper describes the use of generalized valence angles for the screening of pharmacophoric pattern searches in databases of three-dimensional chemical structures. A generalized valence angle is defined as the angle between two vectors, AB and BC, which have a common vertex B, and in which both vectors correspond to formal chemical bonds; one vector corresponds to a bond and the other to a non-bonded interaction; or both vectors correspond to non-bonded interactions. The screens are identified by a statistical analysis of the frequencies of occurrence of these angle-based features in the Cambridge Structural Database. The occurrence frequencies are discussed and shown to be explicable in terms of small, commonly occurring structural features. The effectiveness of the screens is demonstrated by an extensive series of searches for representative pharmacophoric patterns. The results are compared with those obtained from a similar series of searches using distance-based screens: The latter are found to give a better level of performance, and evidence is presented to suggest that this is due to a high degree of association between the assignments of the angle-based screens.