Efficient and robust three-dimensional pattern matching algorithms using hashing and dynamic programming techniques

The paper presents two algorithms for the pattern matching of three-dimensional protein structures. The first of these algorithms, named the least-squares hashing method, was developed for fast substructure search amongst multiple structures. The hashing technique, which is well known in computer science, is combined with a least-squares fitting technique. The second of these algorithms, named the dynamic matching method, was developed to find the alignment of two protein structures. The dynamic matching method is a combination of a dynamic programming technique and a least-squares technique. The dynamic programming technique is applied in terms of not only local similarities but also global similarities. These algorithms have been implemented and applied to PDB data.<>