Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Finding Compact Structural Motifs
verfasst von : Jianbo Qian, Shuai Cheng Li, Dongbo Bu, Ming Li, Jinbo Xu
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.