Finding compact structural motifs

Protein structural motif detection has important applications in structural genomics. Compared with sequence motifs, structural motifs are more sensitive in revealing the evolutionary relationships among proteins. A variety of algorithms have been proposed to attack this problem. However, they are e...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-08, Vol.410 (30), p.2834-2839
Main Authors: Bu, Dongbo, Li, Ming, Li, Shuai Cheng, Qian, Jianbo, Xu, Jinbo
Format: Article
Language:English
Subjects:
Approximation algorithm
Compact Structural motif
NP-Hardness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Protein structural motif detection has important applications in structural genomics. Compared with sequence motifs, structural motifs are more sensitive in revealing the evolutionary relationships among proteins. A variety of algorithms have been proposed to attack this problem. However, they are either heuristic without theoretical performance guarantee, or inefficient due to employing exhaustive search strategies. This paper studies a reasonably restricted version of this problem: the compact structural motif problem. We prove that this restricted version is still NP-hard, and we present a polynomial-time approximation scheme to solve it. This is the first approximation algorithm with a guaranteed ratio for the protein structural motif problem. 1 1 A preliminary version of this paper appeared in CPM’2007.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.03.023