Database Systems
Similarity of 3D Surface Segments
Query processing techniques as used in spatial database systems can also be applied to improve the efficiency of docking queries. The search space can be reduced considerably by using efficient indexing techniques. This lowers the number of candidates, which have to be considered in subsequent and more expensive processing steps. In contrast to previous applications of spatial database systems, it is not the location of the objects in space but their surface shape, which is relevant to protein docking.
Feature-based Similarity of Shapes
For determining complementary surface segments, a feature-based approach can be employed. Features represent the shape of a surface invariant with respect to
rotation and translation, for example by characterizing its curvature type (concave, saddle-shaped, convex). As the docking search requires complementary segments to be found, the used features must be complementable as well. For our experiments we used, among others, the Solid Angle (SA) [EKW96] [Wirth95].
The SA is a measure for the local convexity (or concavity) of a molecule in the neighborhood of a point p of its surface. It can be determined numerically by distributing points on the surface of a sphere and placing its center at point p. Then the number of points inside the molecule is determined and calibrated to get the SA at point p. It can easily be complemented by completing it to the total number of points on the sphere.
In order to characterize a surface segment, first features for selected surface points are calculated. Then concise shape descriptors have to be derived from the feature distribution of the segment. We are investigating if data reducing transforms, like the Fourier transform can be used for this purpose.
In order to perform a docking query, shape descriptors for all surface segments of the query molecule are computed. They are used for a search of complementary
segments in the database [EKSX95].
Shape Similarity based of Surface Approximation
As a competitive approach, we approximate the segments by simple geometric models. As approximation models, we use surface functions like paraboloids of various degrees, and trigonometric polynomials. The similarity of two segments s1 and s2 is measured by the mutual approximation error.
Given an approximation model, like a paraboloid in the example, for both segments s1 and s2, the approximations app1 and app2 are computed by a "least squares" method. To calculate the distance of s1 and s2 the segments mutually are compared to the corresponding approximation of the other segment. The distance
is defined to be the sum of the mutual approximation errors. As a refinement, also the quality of the approximation will be considered.
Figure 3: Geometric approximation and 3D shape similarity
First experiments that we performed on well-known molecular complexes from the PDB (Brookhaven Protein Data Bank) have shown the appropriacy of our distance function with respect to an effective preselection of docking candidates in a protein database system.
In addition, we investigate query processing by multi-step methods, in order to efficiently support shape similarity queries for 3D surface segments based on the similarity defined as above. In the filter step, high-dimensional spatial query objects are to be managed efficiently which will be done by multi-dimensional index structures.
HOME Pages:
DBS
Institute
LMU
Bei Problemen oder Vorschlägen wenden Sie sich bitte an:
wwwmaster@dbs.informatik.uni-muenchen.de
Last Modified: