Poleksic Aleksandar
Department of Computer Science, University of Northern Iowa, Cedar Falls, Iowa 50613, USA.
J Bioinform Comput Biol. 2011 Jun;9(3):367-82. doi: 10.1142/s0219720011005562.
The problem of finding an optimal structural alignment for a pair of superimposed proteins is often amenable to the Smith-Waterman dynamic programming algorithm, which runs in time proportional to the product of lengths of the sequences being aligned. While the quadratic running time is acceptable for computing a single alignment of two fixed protein structures, the time complexity becomes a bottleneck when running the Smith-Waterman routine multiple times in order to find a globally optimal superposition and alignment of the input proteins. We present a subquadratic running time algorithm capable of computing an alignment that optimizes one of the most widely used measures of protein structure similarity, defined as the number of pairs of residues in two proteins that can be superimposed under a predefined distance cutoff. The algorithm presented in this article can be used to significantly improve the speed-accuracy tradeoff in a number of popular protein structure alignment methods.
为一对叠加的蛋白质找到最优结构比对的问题通常可以用史密斯-沃特曼动态规划算法解决，该算法的运行时间与待比对序列长度的乘积成正比。虽然二次运行时间对于计算两个固定蛋白质结构的单个比对来说是可以接受的，但当多次运行史密斯-沃特曼例程以找到输入蛋白质的全局最优叠加和比对时，时间复杂度就成了瓶颈。我们提出了一种次二次运行时间算法，它能够计算一种比对，该比对优化了蛋白质结构相似性最广泛使用的度量之一，该度量定义为在预定义距离截止值下两个蛋白质中可叠加的残基对的数量。本文提出的算法可用于显著改善许多流行蛋白质结构比对方法中的速度-准确性权衡。
