中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Finding compact structural motifs

文献类型：期刊论文

作者Bu, Dongbo2,3; Li, Ming2; Li, Shuai Cheng2; Qian, Jianbo2; Xu, Jinbo1
刊名THEORETICAL COMPUTER SCIENCE
出版日期2009-08-20
卷号410期号:30-32页码:2834-2839
关键词Compact Structural motif NP-Hardness Approximation algorithm
ISSN号0304-3975
DOI10.1016/j.tcs.2009.03.023
英文摘要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.
资助项目Canada ResearchChairs program
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000268617400006
出版者ELSEVIER SCIENCE BV
源URL[http://119.78.100.204/handle/2XEOYT63/11693]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Li, Ming
作者单位1.Toyota Technol Inst Chicago, Chicago, IL 60637 USA
2.Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。