ALGORITHMS FOR LOCAL STRUCTURAL ALIGNMENT AND STRUCTURAL MOTIF IDENTIFICATION
A protein is characterized by both the amino-acid sequence and the three-dimensional (3-D) structure of the underlying atoms. Although it is a common practice of the biologists to use sequence similarity among different proteins to identify any conserved regions during the evolution, it has been proven that the 3-D structures of the proteins are conserved more fundamentally than the sequence during the evolution. Even though two given proteins may not exhibit much of a sequence homology, the structural similarity between them might account for similar properties. Proteins with a similar structure might have similar properties . This is the motivation behind the study of the structural alignment problem in a manner similar to that of the sequence alignment problem .
The structural alignment problem has received immense attention in the past few decades, especially with the increasing number of tertiary structures available in the Protein Data Bank (PDB) . Given two proteins P1 and P2, the problem of structural alignment is to find a highly similar substructure Ssubbetween P1 and P2. The number of known protein structures has increased drastically from 10,000 in 1999 to 45,000 in 2007. This growth makes manual structural alignment almost impossible, and hence, we need algorithms that can yield almost similar ...