期刊
JOURNAL OF COMPUTATIONAL BIOLOGY
卷 14, 期 2, 页码 131-143出版社
MARY ANN LIEBERT, INC
DOI: 10.1089/cmb.2007.0004
关键词
shape matching; molecular structures; contact maps; graph theory
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 R-3, 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 sigma where sigma = min{sigma( P-1), sigma( P-2)} <= O( n(1/2)) is a decomposition parameter depending on the input polygonal chains P-1 and P-2. In R-2, we improve the running time of the previous best known approximation algorithm from O(n(6)) to O(n(3) 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(epsilon)), for some epsilon > 0, is hard.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据