Toh H
Biomolecular Engineering Research Institute, Osaka, Japan.
Comput Appl Biosci. 1997 Aug;13(4):387-96. doi: 10.1093/bioinformatics/13.4.387.
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. Another approximation is associated with the distance cut-off, which is referred to here as the delta 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 delta N cut-off was introduced based on the idea. If the difference between the numbers of the constituent residues of two local environments is greater than a given threshold value, delta 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 epsilon-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 epsilon-suboptimal region to produce an improved alignment.
为了减少结构比对的计算时间，在双动态规划算法中引入了两种近似方法。其中一种是所谓的距离截止，它通过每个残基的局部环境来近似描述其结构环境。在这种近似方法中，以给定半径的球体置于每个残基侧链的中心。残基的局部环境仅由球体内部存在的侧链中心的残基构成，这通过从该残基侧链到所有其他组成残基侧链的一组中心距来表示。球体外部的残基被排除在局部环境之外。另一种近似方法与距离截止相关，在此称为增量N截止。如果两个局部环境彼此相似，那么构成这些环境的残基数量预计也相似。增量N截止就是基于这个想法引入的。如果两个局部环境的组成残基数量之差大于给定阈值增量N，则跳过对局部环境之间相似性的评估。这两种近似方法的引入显著减少了双动态规划算法进行结构比对的计算时间。然而，这些近似方法也降低了比对的准确性。为了在使用近似方法的同时提高准确性，构建了一个具有两步比对算法的程序。首先，使用近似方法大致构建一个比对。然后，确定该比对的ε次优区域。最后，将具有完整结构环境的双动态规划算法应用于ε次优区域内的残基对，以生成改进的比对。
