Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/443743
Title: An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks
Authors: Lin, Guohui;Xu, Dong;Chen, Zhi Zhong;Jiang, Tao;Wen, Jianjun;Xu, Ying
subject: "greedy" algorithm;NMR;bipartite matching;branch-and-bound;chemical shift;combinatorial technique;peak assignment;protein structure
Year: 2008
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 our recent work towards 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 and 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.
Description: 
URI: http://localhost/handle/Hannan/374323
http://localhost/handle/Hannan/443743
ISSN: 076951653X
Appears in Collections:2002-2008

Files in This Item:
File SizeFormat 
AL493070.pdf248.91 kBAdobe PDF
Title: An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks
Authors: Lin, Guohui;Xu, Dong;Chen, Zhi Zhong;Jiang, Tao;Wen, Jianjun;Xu, Ying
subject: "greedy" algorithm;NMR;bipartite matching;branch-and-bound;chemical shift;combinatorial technique;peak assignment;protein structure
Year: 2008
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 our recent work towards 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 and 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.
Description: 
URI: http://localhost/handle/Hannan/374323
http://localhost/handle/Hannan/443743
ISSN: 076951653X
Appears in Collections:2002-2008

Files in This Item:
File SizeFormat 
AL493070.pdf248.91 kBAdobe PDF
Title: An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks
Authors: Lin, Guohui;Xu, Dong;Chen, Zhi Zhong;Jiang, Tao;Wen, Jianjun;Xu, Ying
subject: "greedy" algorithm;NMR;bipartite matching;branch-and-bound;chemical shift;combinatorial technique;peak assignment;protein structure
Year: 2008
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 our recent work towards 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 and 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.
Description: 
URI: http://localhost/handle/Hannan/374323
http://localhost/handle/Hannan/443743
ISSN: 076951653X
Appears in Collections:2002-2008

Files in This Item:
File SizeFormat 
AL493070.pdf248.91 kBAdobe PDF