A geometric algorithm to find small but highly similar 3D substructures in proteins.

Motivation: Most biological actions of proteins depend on some typical parts of their three-dimensional structure, called 3D motifs. It is desirable to find automatically common geometric substructures between proteins to discover similarities in new structures or to model precisely a particular motif. Most algorithms for structural comparison of proteins deal with large (fold) similarities. Here, we focus on small but precise similarities.

Results: We propose a new 3D substructure matching algorithm based on geometric hashing techniques. The key feature of the method is the introduction of a 3D reference frame attached to each residue. This allows us to reduce drastically the complexity of the recognition. Our experimental results confirm the validity of the approach and allow us to find smaller similarities than previous methods.

Availability: The program uses commercial libraries and thus cannot be completely freely distributed. It can be found at ftp://www.inria.fr in the directory epidaure/Outgoing/xpennec/Prospect, but it requires a key to be run, available by request to xavier.pennec@sophia.inria.fr

Contact: Xavier.Pennec@sophia.inria.fr; Nicholas.Ayache@sophia.inria.fr