Fast Molecular Shape Matching Using Contact Maps

Abstract

In this paper, we study the problem of computing the similarity of two protein structures by measuring their contact-map overlap. Contact-map overlap abstracts the problem of computing the similarity of two polygonal chains as a graph-theoretic problem. In , we present the first polynomial time algorithm with any guarantee on the approximation ratio for the 3-dimensional problem. More precisely, we give an algorithm for the contact-map overlap problem with an approximation ratio of σ where σ = min{σ(P ₁), σ(P ₂)} ≤ O(n ^1/2) is a decomposition parameter depending on the input polygonal chains P ₁ and P ₂. In , we improve the running time of the previous best known approximation algorithm from O(n ⁶) to O(n ³ log n) at the cost of decreasing the approximation ratio by half.We also give hardness results for the problem in three dimensions, suggesting that approximating it better than O(n ^∊), for some ∊ > 0, is hard.