NVR-BIP: Nuclear vector replacement using binary integer programming for NMR structure-based assignments

Nuclear magnetic resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure in solution and to identify important sites in a protein. An important bottleneck in NMR protein structure determination is the assignment of NMR peaks to the corresponding nuclei. Structure-based assignment (SBA) aims to solve this problem with the help of a template protein which is homologous to the target and has applications in the study of structure-activity relationship, protein-protein and protein-ligand interactions. We formulate SBA as a linear assignment problem with additional Nuclear Overhauser Effect (NOE) constraints, which can be solved within Nuclear Vector Replacement´s (NVR) framework. Our approach uses NVR´s scoring function and data types, and also gives the option of using CH and NH RDCs, instead of NH RDCs which NVR requires. We test our technique on NVR´s data set as well as on two new proteins. Our results are comparable to NVR´s assignment accuracy on NVR´s test set, but higher on novel proteins. Our approach allows partial assignments. It is also complete and can return the optimum as well as near-optimum assignments. Furthermore, it allows us to analyze the information content of each data type and is easily extendable to accept new forms of input data, such as additional RDCs.