A Hierarchical Grow-and-Match Algorithm for Backbone Resonance Assignments Given 3D Structure

This paper develops an algorithm for NMR backbone resonance assignment given a 3D structure and a set of relatively sparse ¹⁵N-edited NMR data, with the through-space ¹⁵N-edited NOESY as the primary source of information. Our approach supports high-throughput solution studies of dynamics and interactions (e.g., ligand binding), when the structure has previously been determined by crystallography or modeled computationally. We employ a graph matching approach, identifying correspondence between a given contact graph and a corrupted version representing the NMR data. Our hierarchical grow-and-match algorithm decomposes the contact graph into sequential fragments with relatively dense interactions, and then combines possible assignments for the fragments, searching over the combinations with effective but conservative pruning. Our algorithm is complete, guaranteed to identify all solutions consistent with the data within a likelihood threshold of the optimal solution. It also deals correctly and uniformly with missing edges, which are quite common under this formulation. Tests on a number of experimental datasets and simulations with varying noise and sparsity demonstrate that our algorithm can handle significant data corruption (2.5-6.0 noisy edges per correct one) and sparsity (10-40% of the correct edges missing). In addition to the reference solution, the complete ensembles include a number (up to 30) of alternatives. We use these complete ensembles to characterize confidence in parts of an assignment.