Convex Optimization Approaches for NMR Assignment

Abstract

Nuclear Magnetic Resonance Spectroscopy (NMR) is the primary tool for structural determination of proteins in solution. It distinguishes itself from other such tools by uncovering geometric constraints at the atomic level, which are utilized in a maximal constraint satisfaction problem to produce accurate structures without requiring crystallization. Despite its widespread use, full automation of the NMR pipeline has not yet been achieved. Chief among the problematic steps in NMR spectroscopy is the problem of backbone assignment, which can be understood as a labeling step in which atoms are tagged with their resonance frequencies. This labeling is crucial for the construction of structural constraints, and consequently, for the determination of accurate structures.

In this thesis, we describe convex optimization approaches to tackle the combinatorial problem of NMR backbone assignment. These approaches differ from mainstream solutions by seeking to find a single, maximum-likelihood solution via global optimization, rather than attempting to solve non-convex problems through heuristics. Chapter 2 introduces the first such approach, C-SDP, which is, at its core, a semidefinite programming relaxation to the Quadratic Assignment Problem (QAP) with PSD variables of dimension $\mcal{O}(n)\times \mcal{O}(n)$. An efficient distributed ADMM algorithm is described for solving the relaxation to optimality, producing strong lower bounds on several large QAP and TSP problems, and recovering optimal (near rank 1) solutions on NMR datasets. Chapter 3 describes a better scaling, linear programming approach to tackle NMR assignment on both spin system and peak list datasets. The resulting assignment pipeline is successfully applied to both simulated and experimental datasets, with state-of-the-art results on both.