Institute of Computing Technology, Chinese Academy IR
| Finding compact structural motifs | |
| Bu, Dongbo1,3; Li, Ming1; Li, Shuai Cheng1; Qian, Jianbo1; Xu, Jinbo2 | |
| 2009-08-20 | |
| 发表期刊 | THEORETICAL COMPUTER SCIENCE
 |
| ISSN | 0304-3975 |
| 卷号 | 410期号:30-32页码:2834-2839 |
| 摘要 | 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) (C) 2009 Elsevier B.V. All rights reserved. |
| 关键词 | Compact Structural motif NP-Hardness Approximation algorithm |
| DOI | 10.1016/j.tcs.2009.03.023 |
| 收录类别 | SCI |
| 语种 | 英语 |
| 资助项目 | Canada ResearchChairs program |
| WOS研究方向 | Computer Science |
| WOS类目 | Computer Science, Theory & Methods |
| WOS记录号 | WOS:000268617400006 |
| 出版者 | ELSEVIER SCIENCE BV |
| 引用统计 | |
| 文献类型 | 期刊论文 |
| 条目标识符 | http://119.78.100.204/handle/2XEOYT63/11694 |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Li, Ming |
| 作者单位 | 1.Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada 2.Toyota Technol Inst Chicago, Chicago, IL 60637 USA 3.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Bu, Dongbo,Li, Ming,Li, Shuai Cheng,et al. Finding compact structural motifs[J]. THEORETICAL COMPUTER SCIENCE,2009,410(30-32):2834-2839. |
| APA | Bu, Dongbo,Li, Ming,Li, Shuai Cheng,Qian, Jianbo,&Xu, Jinbo.(2009).Finding compact structural motifs.THEORETICAL COMPUTER SCIENCE,410(30-32),2834-2839. |
| MLA | Bu, Dongbo,et al."Finding compact structural motifs".THEORETICAL COMPUTER SCIENCE 410.30-32(2009):2834-2839. |
| 条目包含的文件 | 条目无相关文件。 | |||||
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论