Fast molecular shape matching using contact maps.

Journal Article

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 R3, 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(P1), sigma(P2)} 0, is hard.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Mustafa, NH; Wang, Y

Published Date

  • March 2007

Published In

Volume / Issue

  • 14 / 2

Start / End Page

  • 131 - 143

PubMed ID

  • 17456012

Pubmed Central ID

  • 17456012

Electronic International Standard Serial Number (EISSN)

  • 1557-8666

International Standard Serial Number (ISSN)

  • 1066-5277

Digital Object Identifier (DOI)

  • 10.1089/cmb.2007.0004


  • eng