Special Seminar in Computing + Mathematical Sciences
Annenberg 213
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.
For more information, please contact Sydney Garstang by email at [email protected].