Determining protein structures from NOESY distance constraints by semidefinite programming

Improved NMR-data-compliant protein structure modeling captures context-dependent variations and expands the scope of functional inference

Nuclear magnetic resonance (NMR) spectroscopy can reveal conformational states of a protein in physiological conditions. However, sparsely available NMR data for a protein with large degrees of freedom can introduce structural artifacts in the built models. Currently used state-of-the-art methods deriving protein structure and conformation from NMR deploy molecular dynamics (MD) coupled with simulated annealing for building models. We provide an alternate graph-based modeling approach, where we first build substructures from NMR-derived distance-geometry constraints combined in one shot to form the core structure. The remaining molecule with inadequate data is modeled using a hybrid approach respecting the observed distance-geometry constraints. One-shot structure building is rarely undertaken for large and sparse data systems, but our data-driven bottom-up approach makes this uniquely feasible by suitable partitioning of the problem. A detailed comparison of select models with state-of-art methods reveals differences in the secondary structure regions wherein the correctness of our models is confirmed by NMR data. Benchmarking of 106 protein-folds covering 38-282 length structures shows minimal experimental-constraint violations while conforming to other structure quality parameters such as the proper folding, steric clash, and torsion angle violation based on Ramachandran plot criteria. Comparative MD studies using select protein models from a state-of-art method and ours under identical experimental parameters reveal distinct conformational dynamics that could be attributed to protein structure-function. Our work is thus useful in building enhanced NMR-evidence-based models that encapsulate the contextual secondary and tertiary structure variations present during the experimentation and expand the scope of functional inference.

Protein structure determination using a Riemannian approach

Protein NMR structure determination is one of the most extensively studied problems. Here, we adopt a novel method based on a matrix completion technique - the Riemannian approach - to rebuild the protein structure from the nuclear Overhauser effect distance restraints and the dihedral angle restraints. In comparison with the cyana method, the results generated via the Riemannian approach are more similar to the standard X-ray crystallographic structures as a result of the simple but powerful internal calculation processing function. In addition, our results demonstrate that the Riemannian approach has a comparable or even better performance than the cyana method on other structural assessment metrics, including the stereochemical quality and restraint violations. The Riemannian approach software is available at: https://github.com/xubiaopeng/Protein_Recon_MCRiemman.

Systematic Exploration of Protein Conformational Space Using a Distance Geometry Approach

The optimization approaches classically used during the determination of protein structure encounter various difficulties, especially when the size of the conformational space is large. Indeed, in such a case, algorithmic convergence criteria are more difficult to set up. Moreover, the size of the search space makes it difficult to achieve a complete exploration. The interval branch-and-prune (iBP) approach, based on the reformulation of the distance geometry problem (DGP) provides a theoretical frame for the generation of protein conformations, by systematically sampling the conformational space. When an appropriate subset of interatomic distances is known exactly, this worst-case exponential-time algorithm is provably complete and fixed-parameter tractable. These guarantees, however, immediately disappear as distance measurement errors are introduced. Here we propose an improvement of this approach: threading-augmented interval branch-and-prune (TAiBP), where the combinatorial explosion of the original iBP approach arising from its exponential complexity is alleviated by partitioning the input instances into consecutive peptide fragments and by using self-organizing maps (SOMs) to obtain clusters of similar solutions. A validation of the TAiBP approach is presented here on a set of proteins of various sizes and structures. The calculation inputs are a uniform covalent geometry extracted from force field covalent terms, the backbone dihedral angles with error intervals, and a few long-range distances. For most of the proteins smaller than 50 residues and interval widths of 20°, the TAiBP approach yielded solutions with RMSD values smaller than 3 Å with respect to the initial protein conformation. The efficiency of the TAiBP approach for proteins larger than 50 residues will require the use of nonuniform covalent geometry and may have benefits from the recent development of residue-specific force-fields.

Recovering the Missing Regions in Crystal Structures from the Nuclear Magnetic Resonance Measurement Data Using Matrix Completion Method

Based on matrix completion algorithm, we proposed a simple method to recover the missing regions in the X-ray crystal structures using the corresponding nuclear magnetic resonance (NMR) measurement data for the proteins with both X-ray and NMR experimental data deposited in Protein Data Bank (PDB). By selecting 10 test proteins deposited in PDB and comparing with the standard MODELLER results from the root-mean-square deviation and MolProbity aspects, we validated that our method can provide a better protein structure model, which combines both X-ray crystallographic structure data and NMR data together than MODELLER algorithm. This method is particularly useful for building the initial structures in Molecular Dynamics when studying the protein folding process.

Integrating NOE and RDC using sum-of-squares relaxation for protein structure determination

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 (SDP). However, 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, a hierarchy of convex relaxations with increasing complexity and approximation power. Unlike classical global optimization approaches, SOS optimization returns a certificate of optimality if the global optimum is found. Based on the SOS method, we proposed two algorithms-RDC-SOS and RDC-NOE-SOS, that 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. To the best of our knowledge this is the first time SOS relaxation is introduced to solve non-convex optimization problems in structural biology. We further introduce a statistical tool, the Cramér-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 unbiased estimator. 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 obtained in two alignment media, achieving more accurate and faster reconstructions compared to the current state of the art.

An algorithm to enumerate all possible protein conformations verifying a set of distance constraints

BACKGROUND

The determination of protein structures satisfying distance constraints is an important problem in structural biology. Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature. Most of them, however, are designed to find one solution only.

RESULTS

In order to explore exhaustively the feasible conformational space, we propose here an interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to protein structure determination. This algorithm is based on a discretization of the problem obtained by recursively constructing a search space having the structure of a tree, and by verifying whether the generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used here are directly related to features of protein conformations.

CONCLUSIONS

We described the new algorithm iBP to generate protein conformations satisfying distance constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm iBP has been applied on three α-helical peptides.

Generating conformational transitions using the euclidean distance matrix

Elastic network interpolation (ENI) is an efficient method for generating intermediate conformations between two end protein conformations. Its current formulation uses interatomic distance. We show how this can be generalized to interatomic distances-squared. This generalization is part of an effort to study protein dynamics on the set of positive semidefinite (PSD) matrices, which has a rich mathematical structure. We use lattice structures to test this interpolation scheme, and discuss some limitations observed. We conclude with some suggestions for future research.