An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks

Area of Science:

• Structural Biology
• Biophysics
• Computational Chemistry

Background:

• Nuclear Magnetic Resonance (NMR) resonance assignment is critical for determining protein structures.
• Manual assignment is time-consuming and labor-intensive, often taking weeks.
• Existing computational tools have limitations, leading many labs to prefer manual methods.

Purpose of the Study:

• To develop an automated computational method for NMR backbone resonance assignment.
• To improve the speed and accuracy of the NMR assignment process.
• To provide a robust alternative to manual assignment for protein structure determination.

Main Methods:

• Formulating NMR resonance assignment as a constrained weighted bipartite matching problem.
• Implementing an efficient solution using a branch-and-bound algorithm with advanced bounding techniques.
• Employing a greedy filtering algorithm to optimize the search space.

Main Results:

• The new method significantly outperforms a recently published two-layer algorithm in terms of speed.
• Experimental results on 70 datasets from 14 proteins show higher accuracy in peak assignments.
• The algorithm effectively handles complex NMR data for protein structure analysis.

Conclusions:

• The developed computational method offers a faster and more accurate solution for automated NMR resonance assignment.
• This automation can reduce the time and effort required for protein structure determination using NMR.
• The approach provides a valuable tool for structural biology research, enhancing NMR data analysis.