Maximum Contact Map Overlap Revisited
Maximum Contact Map Overlap Revisited
复制标题
DOI：
10.1089/cmb.2009.0196
复制
发表时间：
2011-01-01
影响因子：
1.7
通讯作者：
Yanev, Nicola
中科院分区：
文献类型：
--
作者：
Andonov, Rumen;Malod-Dognin, Noel;Yanev, Nicola
在量化蛋白质三维结构相似性的方法中，最大接触图重叠（maximum contact map overlap， CMO）在过去十年中一直受到关注。尽管如此，已知的算法表现出适度的性能，并不适用于大规模的比较。本文在这方面提供了一个明确的进展。提出了一种新的CMO整数规划模型，并提出了一种精确分支定界算法，该算法的界由一种新的拉格朗日松弛法得到。该方法的有效性在一个流行的小基准（Skolnick集，40个域）上得到了证明。在这个集合上，我们的算法明显优于现有最好的精确算法。许多困难的CMO实例首次得到了解决。为了进一步评估我们的方法，我们构建了300个蛋白质结构域的大规模集合。计算44850对中的任何一对的相似性度量，我们获得了与SCOP非常一致的分类。补充材料可在www.liebertonline.com/cmb上获得。
Among the measures for quantifying the similarity between three-dimensional (3D) protein structures, maximum contact map overlap (CMO) received sustained attention during the past decade. Despite this, the known algorithms exhibit modest performance and are not applicable for large-scale comparison. This article offers a clear advance in this respect. We present a new integer programming model for CMO and propose an exact branch-and-bound algorithm with bounds obtained by a novel Lagrangian relaxation. The efficiency of the approach is demonstrated on a popular small benchmark (Skolnick set, 40 domains). On this set, our algorithm significantly outperforms the best existing exact algorithms. Many hard CMO instances have been solved for the first time. To further assess our approach, we constructed a large-scale set of 300 protein domains. Computing the similarity measure for any of the 44850 pairs, we obtained a classification in excellent agreement with SCOP. Supplementary Material is available at www.liebertonline.com/cmb.