Geometric Algorithms for Protein Structure Determination Using Measurements From Nuclear Magnetic Resonance Spectroscopy

In an environment such as a cell, the three-dimensional structure of a protein entirely determines its function. Hence, to understand the mechanics of biochemical processes necessary to sustain life, it is crucial to study the structures of proteins at atomic detail. When life is threatened by viral and bacterial pathogens, structural characterization of the proteins at play yields insights about possible treatments and therapeutics. Measurements from nuclear magnetic resonance spectroscopy (NMR) reveal information about the structures of proteins, but building accurate atomic-resolution models from such measurements is an arduous task. The ambiguity and uncertainty of these measurements, and the challenges of obtaining a sufficient number of measurements to uniquely describe a structure, contribute to the difficulty of protein structure determination by NMR.

The current widely-used computational methods using NMR measurements for structure determination primarily rely on various incarnations of stochastic optimization. These techniques have been used to determine protein structures of excellent quality, but in the long term, the reliability of these techniques is dubious (and in cases, demonstrably inadequate), especially as we attempt to solve increasingly difficult structures. Stochastic optimization, due to its random nature, may not always report the best solution. Other superior solutions may lie concealed in the landscape of the objective function and remain undiscovered. We therefore seek computational methods for structure determination that are imbued with guarantees about solution quality. In this dissertation, we present methods for protein structure determination by NMR that are able to guarantee structural solutions quantitatively agree with experimental measurements. Although the trade-off for guaranteeing completeness of algorithms for structure determination is often an exponential running time, for some methods, we remarkably obtained polynomial running times in addition to guarantees of completeness.