Friday, January 29, 2016

3:00 PM -
4:00 PM

Annenberg 213

# Special Seminar in Computing + Mathematical Sciences

Convex Optimization Approaches to Protein Structural Calculation from NMR

Yuehaw Khoo

*,*Physics and Applied Math*,*Princeton University*,*Nuclear magnetic resonance (NMR) spectroscopy is the most-used technique for protein structure determination besides X-ray crystallography. In this talk, two computational problems for NMR spectroscopy will be discussed - protein structuring from residual dipolar coupling (RDC) and the resonance assignment problem.

Typically the 3D structure of a protein is obtained through finding the coordinates of atoms subject to pairwise distance constraints. RDC measurements provide additional geometric information on the angles between bond directions and the principal-axis-frame. The optimization problem involving RDC is non-convex and we present a novel convex programming relaxation to it by incorporating quaternion algebra. In simulations we attain the Cramer-Rao lower bound with relatively efficient running time. From real data, we obtain the protein backbone structure for ubiquitin with 1 Angstrom resolution.

Before calculating the structure, the experimentally measured resonances have to be assigned to specific atoms. We formulate this problem as a quadratic assignment problem (QAP). The QAP problem is NP-hard, and its classical semidefinite programming (SDP) relaxation can only solve problems with about 15 nodes on a standard computer. We present a further relaxation to the QAP problem - Edge-SDP, by associating a reduced-size semidefinite variable to each edge of the graph. Such SDP can be optimized in a distributed fashion via Alternating Direction Method of Multipliers (ADMM). We observe promising results for problems with close to 100 nodes.

These are joint works with Jose Bravo-Ferreira, David Cowburn and Amit Singer.

Event Sponsors:

For more information, please contact Sydney Garstang by email at sydney@caltech.edu.