首页 | 本学科首页   官方微博 | 高级检索  
   检索      


Computational assignment of protein backbone NMR peaks by efficient bounding and filtering
Authors:Lin Guohui  Xu Dong  Chen Zhi-Zhong  Jiang Tao  Wen Jianjun  Xu Ying
Institution:Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8Canada. ghlin@cs.ualberta.ca
Abstract:NMR resonance assignment is one of the key steps in solving an NMR protein structure. The assignment process links resonance peaks to individual residues of the target protein sequence, providing the prerequisite for establishing intra- and inter-residue spatial relationships between atoms. The assignment process is tedious and time-consuming, which could take many weeks. Though there exist a number of computer programs to assist the assignment process, many NMR labs are still doing the assignments manually to ensure quality. This paper presents a new computational method based on the combination of a suite of algorithms for automating the assignment process, particularly the process of backbone resonance peak assignment. We formulate the assignment problem as a constrained weighted bipartite matching problem. While the problem, in the most general situation, is NP-hard, we present an efficient solution based on a branch-and-bound algorithm with effective bounding techniques using two recently introduced approximation algorithms. We also devise a greedy filtering algorithm for reducing the search space. Our experimental results on 70 instances of (pseudo) real NMR data derived from 14 proteins demonstrate that the new solution runs much faster than a recently introduced (exhaustive) two-layer algorithm and recovers more correct peak assignments than the two-layer algorithm. Our result demonstrates that integrating different algorithms can achieve a good tradeoff between backbone assignment accuracy and computation time.
Keywords:
本文献已被 PubMed 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号