Approximate protein structural alignment in polynomial time
Approximate protein structural alignment in polynomial time
复制标题
DOI：
10.1073/pnas.0404383101
复制
发表时间：
2004-08-17
影响因子：
11.1
通讯作者：
Linial, N
中科院分区：
文献类型：
--
作者：
Kolodny, R;Linial, N
蛋白质结构的比对是计算分子生物学的一项基本任务。良好的结构比对可以帮助检测遥远的进化关系，而这些关系很难或不可能仅从蛋白质序列中辨别出来。在这里，我们将结构对齐问题作为一系列优化问题进行研究，并开发了一种近似多项式时间算法来解决它们。对于常用的评分函数，对于长度为 n 的球状蛋白，该算法的运行时间为 O(n(10)/epsilon(6))，并且它检测到在所有最优值中得分在 E 的加性误差内的比对。因此，我们证明这个任务在计算上是可行的，尽管我们引入的方法太慢而无法成为有用的日常工具。我们认为，由于实验确定的蛋白质坐标的噪声性质，这种近似解实际上比精确解更有趣。我们的算法使用的一对蛋白质结构之间的相似性测量涉及结构之间的欧几里德距离（适当严格地转换）。我们证明了一种依赖于内部距离矩阵的替代方法，如果要保证最优性并在多项式时间内运行，则必须结合复杂的几何成分。我们使用这些观察结果来可视化问题的几个实际实例的评分函数。我们的研究深入了解了各种评分函数下蛋白质比对的计算复杂性。这些见解可用于设计可以有效逼近最佳值的评分函数，并且可能用于开发针对多结构对齐问题的有效算法。
Alignment of protein structures is a fundamental task in computational molecular biology. Good structural alignments can help detect distant evolutionary relationships that are hard or impossible to discern from protein sequences alone. Here, we study the structural alignment problem as a family of optimization problems and develop an approximate polynomial-time algorithm to solve them. For a commonly used scoring function, the algorithm runs in O(n(10)/epsilon(6)) time, for globular protein of length n, and it detects alignments that score within an additive error of E from all optima. Thus, we prove that this task is computationally feasible, although the method that we introduce is too slow to be a useful everyday tool. We argue that such approximate solutions are, in fact, of greater interest than exact ones because of the noisy nature of experimentally determined protein coordinates. The measurement of similarity between a pair of protein structures used by our algorithm involves the Euclidean distance between the structures (appropriately rigidly transformed). We show that an alternative approach, which relies on internal distance matrices, must incorporate sophisticated geometric ingredients if it is to guarantee optimality and run in polynomial time. We use these observations to visualize the scoring function for several real instances of the problem. Our investigations yield insights on the computational complexity of protein alignment under various scoring functions. These insights can be used in the design of scoring functions for which the optimum can be approximated efficiently and perhaps in the development of efficient algorithms for the multiple structural alignment problem.