Three-Dimensional Searching for Recurrent Structural Motifs in Data Bases of Protein Structures

The problem of searching a data base of coordinates of proteins for substructures similar to a probe structure or motif is an important problem in computational molecular biology. It is the three-dimensional analog of the one-dimensional case of pattern matching in strings, procedures for which are widely used in molecular biology to search data bases of gene sequences. Typical applications of substructure searching are: (i) Determining whether structural features observed in one protein structure are unique or recurrent, and (ii) in predictions of protein structures, to bridge gaps in an incomplete structural model, by searching the data base for peptides that link the given starting and ending points. We describe our analysis of the problem and our experience in developing software.