  We revisit the problem of protein structure determination from geometrical
restraints from NMR, using convex optimization. It is well-known that the
NP-hard distance geometry problem of determining atomic positions from pairwise
distance restraints can be relaxed into a convex semidefinite program. Often
the NOE distance restraints are too imprecise and sparse for accurate structure
determination. Residual dipolar coupling (RDC) measurements provide additional
geometric information on the angles between atom-pair directions and axes of
the principal-axis-frame. The optimization problem involving RDC is highly
non-convex and requires a good initialization even within the simulated
annealing framework. In this paper, we model the protein backbone as an
articulated structure composed of rigid units. Determining the rotation of each
rigid unit gives the full protein structure. We propose solving the non-convex
optimization problems using the sum-of-squares (SOS) hierarchy. The two
algorithms - RDC-SOS and RDC-NOE-SOS, have polynomial time complexity in the
number of amino-acid residues and run efficiently on a standard desktop. In
many instances, the proposed methods exactly recover the solution to the
original non-convex optimization problem. We introduce a statistical tool, the
Cramer-Rao bound (CRB), to provide an information theoretic bound on the
highest resolution one can hope to achieve when determining protein structure
from noisy measurements using any methodology. Our simulation results show that
when the RDC measurements are corrupted by Gaussian noise of realistic
variance, both SOS based algorithms attain the CRB. We successfully apply our
method in a divide-and-conquer fashion to determine the structure of ubiquitin
from experimental NOE and RDC measurements, achieving more accurate and faster
reconstructions compared to the current state of the art.
