Similarity Search in 3D Protein Databases

Abstract

1 IntroductionWe introduce a new approach for similarity search in 3-D protein databases. By using histograms,we define adaptable similarity models that address the 3-D shape as well as chemical properties of pro-teins. Quadratic forms are employed as similarity distance functions for which efficient query process-ing algorithms are available [Sei 97]. Experimental examples illustrate the applicability of the method.2 Shape Histograms of 3-D ObjectsFor a histogram-based similarity model, we have to decompose the 3-D space into appropriate cells.These cells were used as bins of the histograms. In our primary approach, we distinguish three tech-niques for the decomposition of the 3-D space. Figure 1 illustrates these models in a 2-D projection:• Shell Model: Decomposition into concentric shells around the center point.• Sector Model: Decomposition into sectors that emerge from the center point of the model.• Net-Shaped Model: Decomposition obtained from a combination of shell and sector model. We assume our 3-D objects to be given as sets of points [SK 95]. The histograms are determinedby counting the number of points within each cell. In figure 2, we illustrate various shape histogramsfor the example protein, 1SER-B. In the middle, the space decomposition is indicated schematically,and on the right hand side, the corresponding shape histograms are depicted. The top histogram is