Finding Compact Structural Motifs

Jianbo Qian; Shuai Cheng Li; Dongbo Bu; Ming Li; Jinbo Xu

doi:10.1007/978-3-540-73437-6_16

Finding Compact Structural Motifs

Jianbo Qian
, Shuai Cheng Li
, Dongbo Bu
, Ming Li
, Jinbo Xu

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

7 Citations (Scopus)

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.

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
DOIs	https://doi.org/10.1007/978-3-540-73437-6_16
Publication status	Published - Jul 2007
Externally published	Yes
Event	18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007) - University of Western Ontario, London, Ontario, Canada Duration: 9 Jul 2007 → 11 Jul 2007

Publication series

Name	Lecture Notes in Computer Science
Volume	4580
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007)
Place	Canada
City	London, Ontario
Period	9/07/07 → 11/07/07

Access Output

10.1007/978-3-540-73437-6_16

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{71b702ab2c0442f5be8cf400dfc468ae,

title = "Finding Compact Structural Motifs",

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.",

author = "Jianbo Qian and Li, \{Shuai Cheng\} and Dongbo Bu and Ming Li and Jinbo Xu",

year = "2007",

month = jul,

doi = "10.1007/978-3-540-73437-6\_16",

language = "English",

isbn = "9783540734369",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "142--149",

editor = "Bin Ma and Kaizhong Zhang",

booktitle = "Combinatorial Pattern Matching",

address = "Germany",

note = "18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007) ; Conference date: 09-07-2007 Through 11-07-2007",

}

Qian, J, Li, SC, Bu, D, Li, M & Xu, J 2007, Finding Compact Structural Motifs. in B Ma & K Zhang (eds), Combinatorial Pattern Matching: 18th Annual Symposium, CPM 2007, Proceedings. Lecture Notes in Computer Science, vol. 4580, Springer Verlag, pp. 142-149, 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), London, Ontario, Canada, 9/07/07. https://doi.org/10.1007/978-3-540-73437-6_16

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).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Finding Compact Structural Motifs

AU - Qian, Jianbo

AU - Li, Shuai Cheng

AU - Bu, Dongbo

AU - Li, Ming

AU - Xu, Jinbo

PY - 2007/7

Y1 - 2007/7

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/37849047019

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-37849047019&origin=recordpage

U2 - 10.1007/978-3-540-73437-6_16

DO - 10.1007/978-3-540-73437-6_16

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540734369

SN - 3540734368

T3 - Lecture Notes in Computer Science

SP - 142

EP - 149

BT - Combinatorial Pattern Matching

A2 - Ma, Bin

A2 - Zhang, Kaizhong

PB - Springer Verlag

T2 - 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007)

Y2 - 9 July 2007 through 11 July 2007

ER -

Finding Compact Structural Motifs

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this