Paper Info
Title
On protein structure alignment under distance constraint
Abstract
In this paper we study the protein structure comparison problem where each protein is modeled as a sequence of 3D points, and a contact edge is placed between every two of these points that are sufficiently close. Given two proteins represented this way, our problem is to find a subset of points from each protein, and a bijective matching of points between these two subsets, with the objective of maximizing either (A) the size of the subsets (LCP problem), or (B) the number of edges that exist simultaneously in both subsets (CMO problem), under the requirement that only points within a specified proximity can be matched. It is known that the general CMO problem (without the proximity requirement) is hard to approximate. However, with the proximity requirement, it is known that if a minimum inter-residue distance is imposed on the input, approximate solutions can be efficiently obtained. In this paper we mainly show that the CMO problem under these conditions: (1) is NP-hard, but (2) allows a PTAS. The rest of this paper shows algorithms for the LCP problem which improves on known results.
Year
DOI
Venue
2011
10.1016/j.tcs.2010.11.045
Theoretical Computer Science
Keywords
DocType
Volume
general CMO problem,contact edge,known result,specified proximity,proximity requirement,LCP problem,protein structure comparison problem,approximate solution,distance constraint,Runtime complexity,protein structure alignment,CMO problem,bijective matching,PTAS,Protein structure alignment
Journal
412
Issue
ISSN
Citations 
32
Theoretical Computer Science
9
PageRank 
References 
Authors
0.68
13
2
Name
Order
Citations
PageRank
Shuai Cheng Li118430.25
Yen Kaow Ng2739.46