Saqi M A, Sternberg M J
Biomolecular Modelling Laboratory, Imperial Cancer Research Fund, London, U.K.
J Mol Biol. 1991 Jun 20;219(4):727-32. doi: 10.1016/0022-2836(91)90667-u.
A major problem in sequence alignments based on the standard dynamic programming method is that the optimal path does not necessarily yield the best equivalencing of residues assessed by structural or functional criteria. An algorithm is presented that finds suboptimal alignments of protein sequences by a simple modification to the standard dynamic programming method. The standard pairwise weight matrix elements are modified in order to penalize, but not eliminate, the equivalencing of residues obtained from previous alignments. The algorithm thereby yields a limited set of alternate alignments that can differ considerably from the optimal. The approach is benchmarked on the alignments of immunoglobulin domains. Without a prior knowledge of the optimal choice of gap penalty, one of the suboptimal alignments is shown to be more accurate than the optimal.
基于标准动态规划方法的序列比对中的一个主要问题是，最优路径不一定能产生根据结构或功能标准评估的最佳残基等效性。本文提出了一种算法，通过对标准动态规划方法进行简单修改来找到蛋白质序列的次优比对。修改标准的成对权重矩阵元素，以便惩罚但不消除从先前比对中获得的残基等效性。该算法由此产生一组有限的替代比对，这些比对可能与最优比对有很大差异。该方法在免疫球蛋白结构域的比对上进行了基准测试。在没有事先了解空位罚分的最佳选择的情况下，其中一个次优比对被证明比最优比对更准确。
