Tatsuya Akutsu (akutsu@mel.go.jp)
Mechanical Engineering Laboratory 1-2 Namiki, Tsukuba, Ibaraki 305 Japan
In this paper, we consider the pattern matching problems for three dimensional protein structures. Especially, we consider the problems of substructure search and common substructure search. First, we show that the common substructure search problem amongst multiple protein structures is very difficult from a theoretical viewpoint of computational complexity. Next, we present two practical algorithms. One is named a least-squares hashing method and the other is named a dynamic matching method. In the least-squares hashing method, the hashing technique, which is well-known in computer science, is combined with a least-squares fitting technique. In the dynamic matching method, the dynamic programming technique, which is widely used for pattern matching of DNA and amino acid sequences, is combined with a least-squares fitting technique. These two methods have been applied to PDB (Protein Data Bank) data and shown to be effective.