Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01xk81jp15z
 Title: Convex Optimization Approaches for NMR Assignment Authors: Simoes Bravo Ferreira, Jose Frederico Advisors: Singer, Amit Contributors: Applied and Computational Mathematics Department Keywords: Convex optimizationLinear programmingNMR spectroscopySemidefinite programming Subjects: Applied mathematics Issue Date: 2018 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01xk81jp15z Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Applied and Computational Mathematics