Finding Compact Structural Motifs
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
Author(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | Combinatorial Pattern Matching |
| Subtitle of host publication | 18th Annual Symposium, CPM 2007, Proceedings |
| Editors | Bin Ma, Kaizhong Zhang |
| Publisher | Springer Verlag |
| Pages | 142-149 |
| ISBN (print) | 9783540734369, 3540734368 |
| Publication status | Published - Jul 2007 |
| Externally published | Yes |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 4580 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Conference
| Title | 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007) |
|---|---|
| Location | University of Western Ontario |
| Place | Canada |
| City | London, Ontario |
| Period | 9 - 11 July 2007 |
Link(s)
Abstract
Protein structure motif detection is one of the fundamental problems in Structural Bioinformatics. Compared with sequence motifs, structural motifs are more sensitive in detecting 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 for employing an exhaustive search strategy. Here, we study a reasonably restricted version of this problem: the compact structural motif problem. In this paper, we prove that this restricted version is still NP-hard, and we present a polynomial-time approximation scheme to solve it. To the best of our knowledge, this is the first approximation algorithm with a guarantee ratio for the protein structural motif problem.
Citation Format(s)
Finding Compact Structural Motifs. / Qian, Jianbo; Li, Shuai Cheng; Bu, Dongbo et al.
Combinatorial Pattern Matching: 18th Annual Symposium, CPM 2007, Proceedings. ed. / Bin Ma; Kaizhong Zhang. Springer Verlag, 2007. p. 142-149 (Lecture Notes in Computer Science; Vol. 4580).
Combinatorial Pattern Matching: 18th Annual Symposium, CPM 2007, Proceedings. ed. / Bin Ma; Kaizhong Zhang. Springer Verlag, 2007. p. 142-149 (Lecture Notes in Computer Science; Vol. 4580).
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
