Myers E W, Huang X
Department of Computer Science, University of Arizona, Tucson 85721.
Bull Math Biol. 1992 Jul;54(4):599-618. doi: 10.1007/BF02459636.
We present an O (R log P) time, O (M+P2) space algorithm for searching a restriction map with M sites for the best matches to a shorter map with P sites, where R, the number of matching site pairs, is bounded by MP. As first proposed by Waterman et al. (1984, Nucl. Acids Res. 12, 237-242) the objective function used to score matches is additive in the number of unaligned sites and the discrepancies in the distances between adjacent aligned sites. Our algorithm is basically a sparse dynamic programming computation in which "candidate lists" are used to model the future contribution of all previously computed entries to those yet to be computed. A simple modification to the algorithm computes the distance between two restriction maps with M and N sites, respectively, in O (MN (log M+log N)) time.
我们提出了一种时间复杂度为O (R log P)、空间复杂度为O (M + P2)的算法，用于在具有M个位点的限制酶切图谱中搜索与具有P个位点的较短图谱的最佳匹配，其中匹配位点对的数量R受限于MP。正如沃特曼等人（1984年，《核酸研究》12卷，237 - 242页）首次提出的那样，用于对匹配进行评分的目标函数是未对齐位点的数量以及相邻对齐位点之间距离差异的累加。我们的算法本质上是一种稀疏动态规划计算，其中使用“候选列表”来模拟所有先前计算的条目对尚未计算的条目的未来贡献。对该算法进行简单修改后，可以在O (MN (log M + log N))时间内分别计算具有M个和N个位点的两个限制酶切图谱之间的距离。
