Introduction of a distance cut-off into structural alignment by the double dynamic programming algorithm
Biomolecular Engineering Research Institute 6-2-3, Furuedai. Suita, Osaka 565, Japan E-mail:toh{at}beri.co.jp
Two approximations were introduced into the double dynamic programming algorithm, in order to reduce the computational time for structural alignment. One of them was the so-called distance cut-off, which approximately describes the structural environment of each residue by its local environment. In the approximation, a sphere with a given radius is placed at the center of the side chain of each residue. The local environment of a residue is constituted only by the residues with side chain centers that are present within the sphere, which is expressed by a set of center-to-center distances from the side chain of the residue to those of all the other constituent residues. The residues outside the sphere are neglected from the local environment. An other approximation is associated with the distance cut-ofl which is referred to here as the 
N cut-off. If two local environments are similar to each other, the numbers of residues constituting the environments are expected to be similar.The N cut-off was introduced based on the idea. I f the difference between the numbers of the constituent residues of two local environments is greater than a given threshold value, N, the evaluation of the similarity between the local environments is skipped. The introduction of the two approximations dramatically reduced the computational time for structural alignment by the double dynamic programming algorithm. However, the approximations also decreased the accuracy of the alignment. To improve the accuracy with the approximations, a program with a two-step alignment algorithm was constructed. At first, an alignment was roughly constructed with the approximations. Then, the 
-suboptimal region for the alignment was determined. Finally, the double dynamic programming algorithm with full structural environments was applied to the residue pairs within the -suboptimal region to produce an improved alignment.
Received on November 5, 1996; accepted on February 5, 1997
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Katoh and H. Toh Recent developments in the MAFFT multiple sequence alignment program Brief Bioinform, July 1, 2008; 9(4): 286 - 298. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Daiyasu, T. Ishikawa, K.-i. Kuma, S. Iwai, T. Todo, and H. Toh Identification of cryptochrome DASH from vertebrates Genes Cells, May 1, 2004; 9(5): 479 - 495. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Daiyasu, T. Hiroike, Y. Koga, and H. Toh Analysis of membrane stereochemistry with homology modeling of sn-glycerol-1-phosphate dehydrogenase Protein Eng. Des. Sel., December 1, 2002; 15(12): 987 - 995. [Abstract] [Full Text] [PDF]
|
|