The VSGB 2.0 model: a next generation energy model for high resolution protein structure modeling

A novel energy model (VSGB 2.0) for high resolution protein structure modeling is described, which features an optimized implicit solvent model as well as physics‐based corrections for hydrogen bonding, π–π interactions, self‐contact interactions, and hydrophobic interactions. Parameters of the VSGB 2.0 model were fit to a crystallographic database of 2239 single side chain and 100 11–13 residue loop predictions. Combined with an advanced method of sampling and a robust algorithm for protonation state assignment, the VSGB 2.0 model was validated by predicting 115 super long loops up to 20 residues. Despite the dramatically increasing difficulty in reconstructing longer loops, a high accuracy was achieved: all of the lowest energy conformations have global backbone RMSDs better than 2.0 Å from the native conformations. Average global backbone RMSDs of the predictions are 0.51, 0.63, 0.70, 0.62, 0.80, 1.41, and 1.59 Å for 14, 15, 16, 17, 18, 19, and 20 residue loop predictions, respectively. When these results are corrected for possible statistical bias as explained in the text, the average global backbone RMSDs are 0.61, 0.71, 0.86, 0.62, 1.06, 1.67, and 1.59 Å. Given the precision and robustness of the calculations, we believe that the VSGB 2.0 model is suitable to tackle “real” problems, such as biological function modeling and structure‐based drug discovery. Proteins 2011; © 2011 Wiley‐Liss, Inc.     

A hierarchical approach to all-atom protein loop prediction

The application of all-atom force fields (and explicit or implicit solvent models) to protein homology-modeling tasks such as side-chain and loop prediction remains challenging both because of the expense of the individual energy calculations and because of the difficulty of sampling the rugged all-atom energy surface. Here we address this challenge for the problem of loop prediction through the development of numerous new algorithms, with an emphasis on multiscale and hierarchical techniques. As a first step in evaluating the performance of our loop prediction algorithm, we have applied it to the problem of reconstructing loops in native structures; we also explicitly include crystal packing to provide a fair comparison with crystal structures. In brief, large numbers of loops are generated by using a dihedral angle-based buildup procedure followed by iterative cycles of clustering, side-chain optimization, and complete energy minimization of selected loop structures. We evaluate this method by using the largest test set yet used for validation of a loop prediction method, with a total of 833 loops ranging from 4 to 12 residues in length. Average/median backbone root-mean-square deviations (RMSDs) to the native structures (superimposing the body of the protein, not the loop itself) are 0.42/0.24 A for 5 residue loops, 1.00/0.44 A for 8 residue loops, and 2.47/1.83 A for 11 residue loops. Median RMSDs are substantially lower than the averages because of a small number of outliers; the causes of these failures are examined in some detail, and many can be attributed to errors in assignment of protonation states of titratable residues, omission of ligands from the simulation, and, in a few cases, probable errors in the experimentally determined structures. When these obvious problems in the data sets are filtered out, average RMSDs to the native structures improve to 0.43 A for 5 residue loops, 0.84 A for 8 residue loops, and 1.63 A for 11 residue loops. In the vast majority of cases, the method locates energy minima that are lower than or equal to that of the minimized native loop, thus indicating that sampling rarely limits prediction accuracy. The overall results are, to our knowledge, the best reported to date, and we attribute this success to the combination of an accurate all-atom energy function, efficient methods for loop buildup and side-chain optimization, and, especially for the longer loops, the hierarchical refinement protocol.     

Long loop prediction using the protein local optimization program

We have developed an improved sampling algorithm and energy model for protein loop prediction, the combination of which has yielded the first methodology capable of achieving good results for the prediction of loop backbone conformations of 11 residue length or greater. Applied to our newly constructed test suite of 104 loops ranging from 11 to 13 residues, our method obtains average/median global backbone root-mean-square deviations (RMSDs) to the native structure (superimposing the body of the protein, not the loop itself) of 1.00/0.62 A for 11 residue loops, 1.15/0.60 A for 12 residue loops, and 1.25/0.76 A for 13 residue loops. Sampling errors are virtually eliminated, while energy errors leading to large backbone RMSDs are very infrequent compared to any previously reported efforts, including our own previous study. We attribute this success to both an improved sampling algorithm and, more critically, the inclusion of a hydrophobic term, which appears to approximately fix a major flaw in SGB solvation model that we have been employing. A discussion of these results in the context of the general question of the accuracy of continuum solvation models is presented.     

Fast de novo discovery of low‐energy protein loop conformations

In the prediction of protein structure from amino acid sequence, loops are challenging regions for computational methods. Since loops are often located on the protein surface, they can have significant roles in determining protein functions and binding properties. Loop prediction without the aid of a structural template requires extensive conformational sampling and energy minimization, which are computationally difficult. In this article we present a new de novo loop sampling method, the Parallely filtered Energy Targeted All‐atom Loop Sampler (PETALS) to rapidly locate low energy conformations. PETALS explores both backbone and side‐chain positions of the loop region simultaneously according to the energy function selected by the user, and constructs a nonredundant ensemble of low energy loop conformations using filtering criteria. The method is illustrated with the DFIRE potential and DiSGro energy function for loops, and shown to be highly effective at discovering conformations with near‐native (or better) energy. Using the same energy function as the DiSGro algorithm, PETALS samples conformations with both lower RMSDs and lower energies. PETALS is also useful for assessing the accuracy of different energy functions. PETALS runs rapidly, requiring an average time cost of 10 minutes for a length 12 loop on a single 3.2 GHz processor core, comparable to the fastest existing de novo methods for generating an ensemble of conformations. Proteins 2017; 85:1402–1412. © 2017 Wiley Periodicals, Inc.     

Antibodies as a model system for comparative model refinement

Predicting the conformations of loops is a critical aspect of protein comparative (homology) modeling. Despite considerable advances in developing loop prediction algorithms, refining loops in homology models remains challenging. In this work, we use antibodies as a model system to investigate strategies for more robustly predicting loop conformations when the protein model contains errors in the conformations of side chains and protein backbone surrounding the loop in question. Specifically, our test system consists of partial models of antibodies in which the “scaffold” (i.e., the portion other than the complementarity determining region, CDR, loops) retains native backbone conformation, whereas the CDR loops are predicted using a combination of knowledge‐based modeling (H1, H2, L1, L2, and L3) and ab initio loop prediction (H3). H3 is the most variable of the CDRs. Using a previously published method, a test set of 10 shorter H3 loops (5–7 residues) are predicted to an average backbone (N? Cα? C? O) RMSD of 2.7 Å while 11 longer loops (8–9 residues) are predicted to 5.1 Å, thus recapitulating the difficulties in refining loops in models. By contrast, in control calculations predicting the same loops in crystal structures, the same method reconstructs the loops to an average of 0.5 and 1.4 Å for the shorter and longer loops, respectively. We modify the loop prediction method to improve the ability to sample near‐native loop conformations in the models, primarily by reducing the sensitivity of the sampling to the loop surroundings, and allowing the other CDR loops to optimize with the H3 loop. The new method improves the average accuracy significantly to 1.3 Å RMSD and 3.1 Å RMSD for the shorter and longer loops, respectively. Finally, we present results predicting 8–10 residue loops within complete comparative models of five nonantibody proteins. While anecdotal, these mixed, full‐model results suggest our approach is a promising step toward more accurately predicting loops in homology models. Furthermore, while significant challenges remain, our method is a potentially useful tool for predicting antibody structures based on a known Fv scaffold. Proteins 2010. © 2010 Wiley‐Liss, Inc.     

Accuracy and reliability of the scaling-relaxation method for loop closure: An evaluation based on extensive and multiple copy conformational samplings

The accuracy and reliability of the recently proposed scaling-relaxation method for loop closure were examined by using extensive conformational sampling. For each of the eight heptapeptides chosen to represent a variety of protein conformations, 1,000–2,000 conformations were sampled. Each segment contained 14 rotatable backbone dihedral angles. The average root mean square deviations (RMSDs) between the predicted and the native conformations were 0.7 Å for the backbone and 1.2 Å for the side chain atoms. These predictions were substantially more accurate than the previous predictions (1.1 Å for the backbone and 2.2 Å for the side chain atoms) of the same eight protein segments based on limited conformational sampling (100 conformations for each segment). Large prediction errors mostly occurred at polar and surface side chains that are unlikely to have any meaningful conformation. Moreover, the reliability of seven of the eight predictions was demonstrated with their energy-RMSD and stability-RMSD correlations of the low-energy conformations, where the conformational stability was estimated by using the multiple copy simultaneous sampling method.     

Protein loop selection using orientation-dependent force fields derived by parameter optimization

We used the orientation‐dependent Optimized Side Chain Atomic eneRgy (OSCAR‐o), derived in an early study, for protein loop selection. The prediction accuracy of OSCAR‐o was better than that of physics‐based force fields or statistical potential energy functions for both the RAPPER decoy set and the Jacobson decoy set. The native conformer was frequently ranked as lowest energy among the decoys. Furthermore, strong correlation was observed between the OSCAR‐o score and the root mean square deviation (RMSD) from the native structure for energy‐minimized decoys. In practical use, we applied OSCAR‐o to rescore decoys generated by a widely used loop‐modeling program, LOOPY. As a result, the mean RMSD values of top‐ranked decoys were reduced by 0.3 Å for loop targets of seven to nine residues. We expect similar performance for OSCAR‐o with other loop‐modeling algorithms in the context of decoy rescoring. A loop selection program (OSCAR‐ls) based on OSCAR‐o is available at http://sysimm.ifrec.osaka‐u.ac.jp/OSCAR/ . Proteins 2011; © 2011 Wiley‐Liss, Inc.     

Ab initio structure prediction of the antibody hypervariable H3 loop

Antibodies have the capability of binding a wide range of antigens due to the diversity of the six loops constituting the complementarity determining region (CDR). Among the six loops, the H3 loop is the most diverse in structure, length, and sequence identity. Prediction of the three‐dimensional structures of antibodies, especially the CDR loops, is an important step in the computational design and engineering of novel antibodies for improved affinity and specificity. Although it has been demonstrated that the conformation of the five non‐H3 loops can be accurately predicted by comparing their sequences against databases of canonical loop conformations, no such connection has been established for H3 loops. In this work, we present the results for ab initio structure prediction of the H3 loop using conformational sampling and energy calculations with the program Prime on a dataset of 53 loops ranging in length from 4 to 22 residues. When the prediction is performed in the crystal environment and including symmetry mates, the median backbone root mean square deviation (RMSD) is 0.5 Å to the crystal structure, with 91% of cases having an RMSD of less than 2.0 Å. When the prediction is performed in a noncrystallographic environment, where the scaffold is constructed by swapping the H3 loops between homologous antibodies, 70% of cases have an RMSD below 2.0 Å. These results show promise for ab initio loop predictions applied to modeling of antibodies. © 2012 Wiley Periodicals, Inc.     

Toward better refinement of comparative models: predicting loops in inexact environments

Achieving atomic-level accuracy in comparative protein models is limited by our ability to refine the initial, homolog-derived model closer to the native state. Despite considerable effort, progress in developing a generalized refinement method has been limited. In contrast, methods have been described that can accurately reconstruct loop conformations in native protein structures. We hypothesize that loop refinement in homology models is much more difficult than loop reconstruction in crystal structures, in part, because side-chain, backbone, and other structural inaccuracies surrounding the loop create a challenging sampling problem; the loop cannot be refined without simultaneously refining adjacent portions. In this work, we single out one sampling issue in an artificial but useful test set and examine how loop refinement accuracy is affected by errors in surrounding side-chains. In 80 high-resolution crystal structures, we first perturbed 6-12 residue loops away from the crystal conformation, and placed all protein side chains in non-native but low energy conformations. Even these relatively small perturbations in the surroundings made the loop prediction problem much more challenging. Using a previously published loop prediction method, median backbone (N-Calpha-C-O) RMSD's for groups of 6, 8, 10, and 12 residue loops are 0.3/0.6/0.4/0.6 A, respectively, on native structures and increase to 1.1/2.2/1.5/2.3 A on the perturbed cases. We then augmented our previous loop prediction method to simultaneously optimize the rotamer states of side chains surrounding the loop. Our results show that this augmented loop prediction method can recover the native state in many perturbed structures where the previous method failed; the median RMSD's for the 6, 8, 10, and 12 residue perturbed loops improve to 0.4/0.8/1.1/1.2 A. Finally, we highlight three comparative models from blind tests, in which our new method predicted loops closer to the native conformation than first modeled using the homolog template, a task generally understood to be difficult. Although many challenges remain in refining full comparative models to high accuracy, this work offers a methodical step toward that goal.     

Loopholes and missing links in protein modeling

This paper provides an unbiased comparison of four commercially available programs for loop sampling, Prime, Modeler, ICM, and Sybyl, each of which uses a different modeling protocol. The study assesses the quality of results and examines the relative strengths and weaknesses of each method. The set of loops to be modeled varied in length from 4-12 amino acids. The approaches used for loop modeling can be classified into two methodologies: ab initio loop generation (Modeler and Prime) and database searches (Sybyl and ICM). Comparison of the modeled loops to the native structures was used to determine the accuracy of each method. All of the protocols returned similar results for short loop lengths (four to six residues), but as loop length increased, the quality of the results varied among the programs. Prime generated loops with RMSDs <2.5 A for loops up to 10 residues, while the other three methods met the 2.5 A criteria at seven-residue loops. Additionally, the ability of the software to utilize disulfide bonds and X-ray crystal packing influenced the quality of the results. In the final analysis, the top-ranking loop from each program was rarely the loop with the lowest RMSD with respect to the native template, revealing a weakness in all programs to correctly rank the modeled loops.     

Loop prediction for a GPCR homology model: Algorithms and results

We present loop structure prediction results of the intracellular and extracellular loops of four G‐protein‐coupled receptors (GPCRs): bovine rhodopsin (bRh), the turkey β1‐adrenergic (β1Ar), the human β2‐adrenergic (β2Ar) and the human A2a adenosine receptor (A2Ar) in perturbed environments. We used the protein local optimization program, which builds thousands of loop candidates by sampling rotamer states of the loops' constituent amino acids. The candidate loops are discriminated between with our physics‐based, all‐atom energy function, which is based on the OPLS force field with implicit solvent and several correction terms. For relevant cases, explicit membrane molecules are included to simulate the effect of the membrane on loop structure. We also discuss a new sampling algorithm that divides phase space into different regions, allowing more thorough sampling of long loops that greatly improves results. In the first half of the paper, loop prediction is done with the GPCRs' transmembrane domains fixed in their crystallographic positions, while the loops are built one‐by‐one. Side chains near the loops are also in non‐native conformations. The second half describes a full homology model of β2Ar using β1Ar as a template. No information about the crystal structure of β2Ar was used to build this homology model. We are able to capture the architecture of short loops and the very long second extracellular loop, which is key for ligand binding. We believe this the first successful example of an RMSD validated, physics‐based loop prediction in the context of a GPCR homology model. Proteins 2013. © 2012 Wiley Periodicals, Inc.     

Prediction of a 12-residue loop in bovine pancreatic trypsin inhibitor: effects of buried water

The x-ray conformations of 5-, 7-, 9-, and 12-residue loops in bovine pancreatic trypsin inhibitor (BPTI) were predicted by the use of multiple independent Monte Carlo simulating annealing (MCSA) runs starting from random conformations. Four buried water molecules interacted with a 12-residue loop that started at residue 8 and ended at residue 19, and that included the binding region. The final conformation at the end of an MCSA run was characterized. Solvation free energy based on the solvent accessible surface area was included in the energy function at low simulated annealing temperatures. Conformational states were interactively separated by a recently developed algorithm. Computed loops were characterized in terms of total energy, and backbone and side chain root mean square deviations (RMSDs) between computed native loop conformations and the x-ray conformation. The 12-residue loop was computed with and without buried water [called WL12(8-19) and L12(8-19), respectively]. The backbone was reliably and reproducibly computed to within 1.1 A in L12(8-19) and 0.9 A in WL12(8-19). L12(8-19) required significantly more MCSA runs to achieve the same level of reproducibility as WL12(8-19). Based on the size of the cluster of low energy native loop conformations, and the computational effort, WL12(8-19) had greater entropy. In calculations of 7-, 9-, and 12-residue loops without buried water, the effects of buried water became obvious in the 12-residue loop calculation, which interacted with all four buried water molecules. Nearly all conformations of the native loop conformer had a hydrogen bond between the Lys 15 side chain and the backbone of Gly 12, Pro 13, and Cys 14, which may have implications in the rate of exchange of buried water with bulk solvent and in protein folding. The present version of MCSA program was more efficient than earlier versions.     

Fragment‐based modeling of membrane protein loops: Successes,failures, and prospects for the future

Membrane proteins (MPs) have become a major focus in structure prediction, due to their medical importance. There is, however, a lack of fast and reliable methods that specialize in the modeling of MP loops. Often methods designed for soluble proteins (SPs) are applied directly to MPs. In this article, we investigate the validity of such an approach in the realm of fragment‐based methods. We also examined the differences in membrane and soluble protein loops that might affect accuracy. We test our ability to predict soluble and MP loops with the previously published method FREAD. We show that it is possible to predict accurately the structure of MP loops using a database of MP fragments (0.5–1 Å median root‐mean‐square deviation). The presence of homologous proteins in the database helps prediction accuracy. However, even when homologues are removed better results are still achieved using fragments of MPs (0.8–1.6 Å) rather than SPs (1–4 Å) to model MP loops. We find that many fragments of SPs have shapes similar to their MP counterparts but have very different sequences; however, they do not appear to differ in their substitution patterns. Our findings may allow further improvements to fragment‐based loop modeling algorithms for MPs. The current version of our proof‐of‐concept loop modeling protocol produces high‐accuracy loop models for MPs and is available as a web server at http://medeller.info/fread . Proteins 2014; 82:175–186. © 2013 Wiley Periodicals, Inc.     

RNA loop structure prediction via bond scaling and relaxation

We have developed a method for predicting the structure of small RNA loops that can be used to augment already existing RNA modeling techniques. The method requires no input constraints on loop configuration other than end-to-end distance. Initial loop structures are generated by randomizing the torsion angles, beginning at one end of the polynucleotide chain and correlating each successive angle with the previous. The bond lengths of these structures are then scaled to fit within the known end constraints and the equilibrium bond lengths of the potential energy function are scaled accordingly. Through a series of rescaling and minimization steps the structures are allowed to relax to lower energy configurations with standard bond lengths and reduced van der Waals clashes. This algorithm has been tested on the variable loops of yeast tRNA-Asp and yeast tRNA-Phe, as well as the sarcin-ricin tetraloop and the anticodon loop of yeast tRNA-Phe. The results indicate good correlation between potential energy and the loop structure predictions that are closest to the variable loop crystal structures, but poorer correlation for the more isolated stem loops. The number of stacking interactions has proven to be a good objective measure of the best loop predictions. Selecting on the basis of energy and stacking, we obtain two structures with 0.65 and 0.75 Å all-atom rms deviations (RMSD) from the crystal structure for the tRNA-Asp variable loop. The best structure prediction for the tRNA-Phe variable loop has an all-atom RMSD of 2.2 Å and a backbone RMSD of 1.6 Å, with a single base responsible for most of the deviation. For the sarcin-ricin loop from 28S ribosomal RNA, the predicted structure's all-atom RMSD from the nmr structure is 1.0 Å. We obtain a 1.8 Å RMSD structure for the tRNA-Phe anticodon loop. © 1996 John Wiley & Sons, Inc.     

Crystal structure analysis,covalent docking,and molecular dynamics calculations reveal a conformational switch in PhaZ7 PHB depolymerase

An open and a closed conformation of a surface loop in PhaZ7 extracellular poly(3‐hydroxybutyrate) depolymerase were identified in two high‐resolution crystal structures of a PhaZ7 Y105E mutant. Molecular dynamics (MD) simulations revealed high root mean square fluctuations (RMSF) of the 281–295 loop, in particular at residue Asp289 (RMSF 7.62 Å). Covalent docking between a 3‐hydroxybutyric acid trimer and the catalytic residue Ser136 showed that the binding energy of the substrate is significantly more favorable in the open loop conformation compared to that in the closed loop conformation. MD simulations with the substrate covalently bound depicted 1 Å RMSF higher values for the residues 281–295 in comparison to the apo (substrate‐free) form. In addition, the presence of the substrate in the active site enhanced the ability of the loop to adopt a closed form. Taken together, the analysis suggests that the flexible loop 281–295 of PhaZ7 depolymerase can act as a lid domain to control substrate access to the active site of the enzyme. Proteins 2017; 85:1351–1361. © 2017 Wiley Periodicals, Inc.     

Application of biasing‐potential replica‐exchange simulations for loop modeling and refinement of proteins in explicit solvent

Comparative or homology modeling of a target protein based on sequence similarity to a protein with known structure is widely used to provide structural models of proteins. Depending on the target‐template similarity these model structures may contain regions of limited structural accuracy. In principle, molecular dynamics (MD) simulations can be used to refine protein model structures and also to model loop regions that connect structurally conserved regions but it is limited by the currently accessible simulation time scales. A recently developed biasing potential replica exchange (BP‐REMD) method was used to refine loops and complete decoy protein structures at atomic resolution including explicit solvent. In standard REMD simulations several replicas of a system are run in parallel at different temperatures allowing exchanges at preset time intervals. In a BP‐REMD simulation replicas are controlled by various levels of a biasing potential to reduce the energy barriers associated with peptide backbone dihedral transitions. The method requires much fewer replicas for efficient sampling compared with T‐REMD. Application of the approach to several protein loops indicated improved conformational sampling of backbone dihedral angle of loop residues compared to conventional MD simulations. BP‐REMD refinement simulations on several test cases starting from decoy structures deviating significantly from the native structure resulted in final structures in much closer agreement with experiment compared to conventional MD simulations. Proteins 2010. © 2010 Wiley‐Liss, Inc.     

Steric hindrance controls pyridine nucleotide specificity of a flavin‐dependent NADH:quinone oxidoreductase

The crystal structure of the NADH:quinone oxidoreductase PA1024 has been solved in complex with NAD⁺ to 2.2 Å resolution. The nicotinamide C4 is 3.6 Å from the FMN N5 atom, with a suitable orientation for facile hydride transfer. NAD⁺ binds in a folded conformation at the interface of the TIM‐barrel domain and the extended domain of the enzyme. Comparison of the enzyme‐NAD⁺ structure with that of the ligand‐free enzyme revealed a different conformation of a short loop (75–86) that is part of the NAD⁺‐binding pocket. P78, P82, and P84 provide internal rigidity to the loop, whereas Q80 serves as an active site latch that secures the NAD⁺ within the binding pocket. An interrupted helix consisting of two α‐helices connected by a small three‐residue loop binds the pyrophosphate moiety of NAD⁺. The adenine moiety of NAD⁺ appears to π–π stack with Y261. Steric constraints between the adenosine ribose of NAD⁺, P78, and Q80, control the strict specificity of the enzyme for NADH. Charged residues do not play a role in the specificity of PA1024 for the NADH substrate.     

How noise in force fields can affect the structural refinement of protein models?

Structural refinement of predicted models of biological macromolecules using atomistic or coarse‐grained molecular force fields having various degree of error is investigated. The goal of this analysis is to estimate what is the probability for designing an effective structural refinement based on computations of conformational energies using force field, and starting from a structure predicted from the sequence (using template‐based or template‐free modeling), and refining it to bring the structure into closer proximity to the native state. It is widely believed that it should be possible to develop such a successful structure refinement algorithm by applying an iterative procedure with stochastic sampling and appropriate energy function, which assesses the quality (correctness) of protein decoys. Here, an analysis of noise in an artificially introduced scoring function is investigated for a model of an ideal sampling scheme, where the underlying distribution of RMSDs is assumed to be Gaussian. Sampling of the conformational space is performed by random generation of RMSD values. We demonstrate that whenever the random noise in a force field exceeds some level, it is impossible to obtain reliable structural refinement. The magnitude of the noise, above which a structural refinement, on average is impossible, depends strongly on the quality of sampling scheme and a size of the protein. Finally, possible strategies to overcome the intrinsic limitations in the force fields for impacting the development of successful refinement algorithms are discussed. Proteins 2012. © 2011 Wiley Periodicals, Inc.     

Protein loop closure using orientational restraints from NMR data

Protein loops often play important roles in biological functions. Modeling loops accurately is crucial to determining the functional specificity of a protein. Despite the recent progress in loop prediction approaches, which led to a number of algorithms over the past decade, few rigorous algorithmic approaches exist to model protein loops using global orientational restraints, such as those obtained from residual dipolar coupling (RDC) data in solution nuclear magnetic resonance (NMR) spectroscopy. In this article, we present a novel, sparse data, RDC‐based algorithm, which exploits the mathematical interplay between RDC‐derived sphero‐conics and protein kinematics, and formulates the loop structure determination problem as a system of low‐degree polynomial equations that can be solved exactly, in closed‐form. The polynomial roots, which encode the candidate conformations, are searched systematically, using provable pruning strategies that triage the vast majority of conformations, to enumerate or prune all possible loop conformations consistent with the data; therefore, completeness is ensured. Results on experimental RDC datasets for four proteins, including human ubiquitin, FF2, DinI, and GB3, demonstrate that our algorithm can compute loops with higher accuracy, a three‐ to six‐fold improvement in backbone RMSD, versus those obtained by traditional structure determination protocols on the same data. Excellent results were also obtained on synthetic RDC datasets for protein loops of length 4, 8, and 12 used in previous studies. These results suggest that our algorithm can be successfully applied to determine protein loop conformations, and hence, will be useful in high‐resolution protein backbone structure determination, including loops, from sparse NMR data. Proteins 2012. © 2011 Wiley Periodicals, Inc.