Skip navigation
Please use this identifier to cite or link to this item:
Title: Convex Optimization Approaches for NMR Assignment
Authors: Simoes Bravo Ferreira, Jose Frederico
Advisors: Singer, Amit
Contributors: Applied and Computational Mathematics Department
Keywords: Convex optimization
Linear programming
NMR spectroscopy
Semidefinite 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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
SimoesBravoFerreira_princeton_0181D_12793.pdf3.97 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.