Chapters 15–18Short Course: Automated NMR Assignment and Protein Structure Determination Using Sparse Residual Dipolar Couplings

Bruce R. Donald and Jeffrey Martin

Introduction

By now, the reader will have learned some of the basics, both of NMR physics and the computational algorithms required to interpret the data. Hence, it is possible to pull together some of these concepts in order to build a comprehensive picture of the algorithms and mathematics that can be employed to assign spectra and determine solution-state NMR structures. This chapter addresses a special case, but an important one, namely, that of using sparse data obtained mostly from residual dipolar couplings (RDCs). The subject is mathematically rich, and fertile ground for students and researchers who wish to understand and develop new methodology.

We have organized this material into a longer chapter, which is presented as a “short course”—a discrete module within a semester-long class, or even the bulk of a shorter class in a typical medical school teaching schedule. The exposition is at approximately the same level as the other chapters in this book, but a longer narrative allows us to get a running start, and persistently attack the key computational biophysical problems with a systematic perspective.

Motivation

The introduction of RDCs for protein structure determination in the late 1990s energized development of NMR methods. Robust automation of the complete NMR structure determination procedure has been a longstanding goal, and RDC-based algorithms may increase the consistency and reliability of NMR structural studies. It has also been recognized that structure determination based primarily on orientational restraints could be quicker and more accurate than traditional distance-restraint-based methods. Furthermore, NMR is increasingly important in applications where structural information is already available, so that methods which effectively automate NMR assignment of known structures would also be a substantial contribution.

Since RDCs are measured in a global coordinate frame, they enable molecular replacement–like methods that perform assignments using structural priors. Furthermore, recent methods for structure determination have exploited novel RDC equations, which combine RDC data and protein kinematics. Under fairly mild assumptions, the dihedral torsional angles of a protein can be analytically expressed as roots of these low-degree polynomials. Solving these equations exactly has enabled a departure from earlier stochastic methods, and led to linear-time, combinatorially precise algorithms for NMR structure determination. These algorithms are optimal in terms of combinatorial (but not algebraic) complexity, and show how structural data can be used to produce a deterministic, optimal solution for the protein structure in polynomial time.

The coefficients of the RDC equations are determined by the data. An RDC error bound therefore defines a range of coefficients, which, in turn, yield a range of roots representing the structural dihedral angles. Hence, the RDC equations define an analytical relationship between the RDC error distribution, and the coordinate error of the ensemble of structures that satisfy the experimental restraints. Precise methods that relate the experimental error to the coordinate error of the computed structures therefore appear within reach. In this chapter, we describe these and other recent advances in NMR assignment and structure determination based on sparse dipolar couplings.

Glossary of Abbreviations

We use the following abbreviations in this chapter:

C′C' = carbonyl carbon

CHCH = CαC^\alpha - HαH^\alpha

DOFDOF = degrees of freedom

FF2FF2 = FF domain 2 of human transcription elongation factor CA150 (RNA polymerase II C-terminal domain interacting protein)

hSRIhSRI = human Set2-Rpb1 interacting domain

HSQCHSQC = heteronuclear single quantum coherence spectroscopy

MDMD = molecular dynamics

NMRNMR = nuclear magnetic resonance

NOENOE = nuclear Overhauser effect

PDBPDB = protein Data Bank

POFPOF = principal order frame

polηpol\ \eta = zinc finger domain of the human DNA Y-polymerase Eta

ppmppm = parts per million

RDCRDC = residual dipolar coupling

RMSDRMSD = root mean square deviation

SASA = simulated annealing

SSESSE = secondary structure element

vdWvdW = van der Waals

Background

While automation is revolutionizing many aspects of biology, the determination of three-dimensional (3D) protein structure remains a harder, more expensive task. Novel algorithms and computational methods in biomolecular NMR are necessary to apply modern techniques such as structure-based drug design and structural proteomics on a much larger scale. Traditional (semi-) automated approaches to protein structure determination through NMR spectroscopy require a large number of experiments and substantial spectrometer time, making them difficult to fully automate. A chief bottleneck in determinating 3D protein structures by NMR is the assignment of chemical shifts and NOE restraints in a biopolymer.

The introduction of RDCs for protein structure determination enabled novel attacks on the assignment problem, to expedite high-throughput NMR structure determination. Similarly, it is difficult to determine protein structures accurately using only sparse data. New algorithms have been developed to handle the increased spectral complexity encountered for larger proteins, and sparser information content obtained either in a high-throughput setting, or for larger or difficult proteins. The overall goal is to minimize the number and types of NMR experiments that must be performed and the amount of human effort required to interpret the experimental results, while still producing an accurate analysis of the protein structure.

This short course is tempered by our recent experiences in automated assignments [79, 82, 83, 118, 153, 174], novel algorithms for protein structure determination [152, 156, 117, 89, 110, 151, 155, 154], characterization of protein complexes [118, 99] and membrane proteins [117], and fold recognition using only unassigned NMR data [82, 83, 78, 80]. Recent algorithms for automated assignment and structure determination based on sparse dipolar couplings represent a departure from the stochastic methods frequently employed by the NMR community (e.g., simulated annealing/molecular dynamics (SA/MD), Monte Carlo (MC), etc.) A corollary is that such stochastic methods, now routinely employed in NMR structure determination pipelines [60, 53, 91, 64], should be reconsidered in light of their inability to ensure identification of the unique or globally optimal structural models consistent with a set of NMR observations. In this vein, this short course focuses on sparse data. While SA/MD may perform adequately in a data-rich, highly constrained setting, it is difficult to determine protein structures accurately using only sparse data. Sparse data arises not only in high-throughput settings, but also for larger proteins, membrane proteins [117], symmetric protein complexes [118], and difficult systems including denatured or disordered proteins [154]. Sparse-data algorithms require guarantees of completeness to ensure that solutions are not missed and local minima are evaded.

We caution that in the context of NMR, “high-throughput” is relative, and currently not as rapid as, for example, gene sequencing or even crystallography. Hence the term “batch mode” may be more appropriate. The challenge is to develop new algorithms and computer systems to exploit sparse NMR data, demonstrating the large amount of information available in a few key spectra, and how it can be extracted using a blend of combinatorial and geometric algorithms. Moreover, because of their (relative) experimental simplicity, we hypothesize that the computational advantages offered by such approaches should ultimately obtain an integrated system in which automated assignment and calculation of the global fold could be performed at rates comparable to current-day protein screening for structural genomics using 15N^{15}\text{N} -edited heteronuclear single quantum coherence spectroscopy (15N^{15}\text{N} -HSQC).

This chapter describes how sparse dipolar couplings can be exploited to address key computational bottlenecks in NMR structural biology. The past few years have yielded rapid progress in automated assignments, novel algorithms for protein structure determination, characterization of protein complexes and membrane proteins, and fold recognition using only unassigned NMR data. We discuss recent algorithms that assist these advances, including (1) sparse-data algorithms for protein structure determination from RDCs using exact solutions and systematic search; (2) RDC-based molecular replacement–like techniques for structure-based assignment; (3) structure determination of membrane proteins and complexes, especially symmetric oligomers, enabled by RDCs; and (4) automated assignment of NOE restraints in both monomers and complexes, based on backbones computed primarily using sparse RDC restraints.

These define the four main themes in this chapter.

  1. It is difficult to determine protein structures accurately using only sparse data. Sparse data arises not only in high-throughput settings, but also for larger proteins, membrane proteins, and symmetric protein complexes. For de novo structure determination, there are now roots-of-polynomials approaches to compute exact solutions, by systematic search, for internuclear bond vectors and backbone dihedral angles using as few as 2 recorded RDCs per residue (for example, NH in two media, or NH and Hα-Cα\text{H}^\alpha\text{-C}^\alpha in one medium [177]). By combining systematic search with exact solutions, it is possible to efficiently compute accurate backbone structures using less NMR data than in traditional approaches.

De novo structure determination from sparse dipolar couplings can exploit structure equations derived by Wang and Donald [152, 151]. These include a quartic equation to compute the internuclear (e.g., bond) vectors from as few as 2 recorded RDCs per residue, and quadratic equations to subsequently compute protein backbone (ϕ\phi , ψ\psi) angles exactly [152, 151]. The structure equations make it possible to compute, exactly and in constant time, the backbone (ϕ\phi , ψ\psi) angles for a residue from very sparse RDCs. Simulated annealing, molecular dynamics, energy minimization, and distance geometry are not required, since the structure is computed exactly from the data. Novel algorithms build on these exact solutions, to perform protein structure determination, using mostly RDCs but also sparse NOEs. For example, the RDC-EXACT algorithm employs a systematic search with provable pruning, to determine the conformation of helices, strands, and loops and to compute their orientations using exclusively the angular restraints from RDCs [152, 156, 177]. Then, the algorithm uses very sparse distance restraints between these computed segments of structure, to determine the global fold.

  1. Algorithms using sparse dipolar couplings can accelerate protein NMR assignment and structure determination by exploiting a priori structural information. By analogy, in X-ray crystallography, the molecular replacement (MR) technique allows solution of the crystallographic phase problem when a “close” or homologous structural model is known, thereby facilitating rapid structure determination. In contrast, a key bottleneck in NMR structural biology is the assignment problem — the mapping of spectral peaks to tuples of interacting atoms in a protein. For example, peaks in a 3D nuclear Overhauser enhancement spectroscopy (NOESY) experiment establish distance restraints on a protein’s structure by identifying pairs of protons interacting through space. An automated procedure for rapidly determining NMR assignments given a homologous structure, can similarly accelerate structure determination. Moreover, even when the structure has already been determined by crystallography or computational homology modeling, NMR assignments are valuable because NMR can be used to probe protein-protein interactions and protein-ligand binding (via chemical shift mapping or line-broadening), and dynamics (via, e.g., nuclear spin relaxation). Molecular replacement-like approaches for structure-based assignment of resonances and NOEs, including structure-based assignment (SBA) algorithms, can be applied when a homologous protein is known. Moreover, to find structural homologs, it is possible to apply (filter) modules of SBA to a structure database (as opposed to a single structure). This technique performs rapid fold recognition by correlating structural geometry versus distributions of unassigned NMR data, enabling detection of homologous structures before assignments [82, 83, 78, 145, 97, 80]. Hence, the algorithm finds candidate homologs using only unassigned spectra; then SBA algorithms perform assignments given the structural homolog.

Several algorithms have been proposed for structure-based assignment using RDCs [4, 3, 63, 82, 83, 79, 67, 64]. For example, NVR [79] exploits RDCs to perform structure-based assignment (backbone and NOEs) of proteins when a homologous structure is known, and requires only 15N^{15}\text{N} -labeling. NVR was a step in developing a MR-like method for NMR (useful because many NMR studies, especially in drug design and pharmacology, are of homologous proteins). NVR exploits a priori structural information. Automated procedures for rapidly determining NMR assignments given a homologous structure, can accelerate structure determination, since assignments must generally be obtained before NOEs, chemical shifts, RDCs, and scalar couplings can be employed for structure determination/refinement. NVR offers a high-throughput mechanism for the required assignment process. However, the spectral assignment produced by NVR is itself an important product: even when the structure has already been determined by X-ray crystallography or computational homology modeling, NMR assignments are valuable for structure-activity relation (SAR) by NMR [133, 54] and chemical shift mapping [18], which compare assigned NMR spectra for an isolated protein and a protein:ligand or protein:protein complex. Both are used in high-throughput drug activity screening to determine binding modes. Assignments are also necessary to determine the residues implicated in the dynamics data from nuclear spin relaxation (e.g. [113, 112, 71]). Building on NVR [79], the algorithm GD [78] performs rapid fold recognition (via geometric hashing against a protein structural database) to correlate distributions of unassigned NMR data. GD exploits novel approaches for alignment tensor estimation from unassigned RDCs [78, 82, 83], to perform maximum-likelihood resonance and NOE assignment [80] (in the NVR framework) against the PDB, to detect the fold even before assignments.

In contrast to traditional methods, the set of NMR experiments required by NVR and RDC-EXACT is smaller, and requires less spectrometer time. While these algorithms have exploited uniform 13C^{13}\text{C} -/ 15N^{15}\text{N} -labeling [151, 156], NVR and RDC-EXACT have been successfully applied to experimental spectra from different proteins using only 15N^{15}\text{N} -labeling, a cheaper process than 13C^{13}\text{C} labeling (cf. Wüthrich [166]: “A big asset with regard to future practical applications . . . [is] . . . straightforward, inexpensive experimentation. This applies to the isotope labeling scheme as well as to the NMR spectroscopy . . .”).

  1. We will describe recent algorithms that assist in determining membrane protein structures. In such systems, RDCs serve several functions. First, RDCs enable accurate subunit backbone structure calculation in complexes. Second, in symmetric homo-oligomers, the RDCs aid in determining the symmetry axis [2, 168]. These two advantages enable complete algorithms for NOE assignment and structure determination that overcome limitations of the simulated annealing/molecular dynamics (SA/MD) methodology when the data are sparse. Several methods, including SYMBRANE and AMBIPACK, cast the problem of structure determination for symmetric homo-oligomers (such as many membrane proteins) into a systematic search of symmetry configuration space, automatically assigning NOEs and handling NOE ambiguity while provably characterizing the uncertainty in the structural ensemble [117, 118].

Membrane proteins present experimental and computational challenges. Structural studies can be difficult if a protein is hard to crystallize (for X-ray) or is not well-behaved in an artificial membrane (for NMR). Many membrane proteins are symmetric oligomers. In an n-mer, identical electronic environments obtain identical chemical shifts, thereby boosting each signal approximately n-fold. However, it is not possible to distinguish signals from symmetric atoms in different subunits. The ambiguity in intersubunit NOEs (with identical chemical shifts) adds to the usual chemical shift ambiguity in assigning NOEs in monomers (with ‘merely’ similar shifts). While the latter could, in principle, be resolved experimentally (for example, using 4D NOESY [21]), the former is inherent in the symmetry and cannot currently be resolved by experimental methods: computational solutions are required. On the other hand, the symmetry (which is known to exist from the signal overlap) can be used as an explicit kinematic constraint during structure determination. SYMBRANE is both complete, in that it evaluates all possible conformations, and data-driven, in that it evaluates conformations separately for consistency with experimental data and for quality of packing. Completeness ensures that the algorithm does not miss the native conformation, and being data-driven enables it to assess the structural precision possible from data alone. SYMBRANE performs a branch-and-bound search in the symmetry configuration space. It eliminates structures inconsistent with intersubunit NOEs, and then identifies conformations representing every consistent, well-packed structure. SYMBRANE has been used to determine the complete ensemble of NMR structures of unphosphorylated human cardiac phospholamban [117], a pentameric membrane protein. SYMBRANE addresses some of the challenges of protein complex determination, larger proteins, and the difficulties arising from symmetry and NOE ambiguity. By running SYMBRANE using different priors (starting structures) encoding the putative oligomeric number, one can determine, solely from NMR data, the maximum-likelihood oligomeric state.

  1. Since accurate protein backbone structures can be computed from RDCs, these backbones can then be used to bootstrap NOE assignment. Novel techniques, including the algorithms TRIANGLE [153] and HANA [174], exploit the accurate, high-throughput backbone structures obtained exactly using sparse RDCs. NOE assignment can be difficult to fully automate, and structure determination of symmetric membrane proteins by NMR can be challenging. We discuss how, by combining these two difficult problems, recent results indicate an algorithm that solves both simultaneously, and enjoys guarantees on its completeness and complexity [117, 118].

An overview of the major steps to automated assignment and structure determination using sparse RDCs is given in figure 15.1. The figure suggests how these algorithms and software tools could be developed into a set of integrated programs for automated fold recognition, assignment, monomeric and oligomeric structure determination. For each of the modules in the figure, there are algorithms and implementations reported by several groups working on NMR methodology. One example for each module is shown in the figure, and should be interpreted as a representative for a class of algorithms (described later) with similar function. Fold recognition [82, 83, 78, 145, 97, 80, 128] denotes correlation of unassigned NMR distributions (e.g., RDCs) against a database of known folds. Structure-based assignment (SBA) [4, 3, 63, 82, 83, 79, 67, 64] denotes automated assignment given priors on the putative structure(s) of the protein. Note that, like sparse data and completeness, SBA is a crosscutting theme: NVR uses priors on putative homologs (detected by GD) to assign resonances (and unambiguous HNH^N - HNH^N NOEs). A number of algorithms for protein structure determination are based on exact solutions to the RDC equations [122, 159, 152, 151, 156, 154, 155, 174]. RDC-EXACT is one such algorithm [151, 152, 156]. While the algorithms of [38, 69, 167] are not exact, it is likely that a roots-of-polynomials exact solutions version of these algorithms could be derived, although possibly not in closed-form. TRIANGLE uses backbone structure (computed by RDC-EXACT) to assign ambiguous backbone and side-chain NOEs. Several algorithms exist to determine the structure of symmetric homooligomers using a combination of RDCs, NOEs, and other NMR data [150, 117, 118, 129, 168]. SYMBRANE [117, 118] and AMBIPACK [150] exploit the subunit (monomer) structure to assign intermolecular NOEs and determine the complex structure. Finally, note that assignment (NVR) and Fold Recognition (GD) operate entirely on unassigned data. Structure Determination by RDC-EXACT operates on assigned data.

This chapter concentrates on the information content of the NMR experiments, and the methods for assignment and structure determination, with an emphasis, where possible, on provable algorithms with guarantees of soundness, completeness, and complexity bounds. A number of excellent articles have appeared on the experimental aspects of RDCs; we recommend Weidong and Wang [160] for a good introduction to RDCs and the interplay between experimental and computational challenges.

Rather than describing a competition between computer programs, this chapter tries to evaluate the strengths and weaknesses of the underlying ideas (algorithms). There are several reasons. First, we believe no one will be using the same programs in ten years (and if we are, that would reflect poorly on the field). However, the underlying mathematical relationships between the data and the structures should prove enduring, warranting a characterization of the completeness, soundness, and complexity of structure determination algorithms exploiting sparse dipolar couplings.1

Figure 15.1 Overview of the major modules in automated NMR assignment and protein structure determination using sparse dipolar coupling constraints. One example for each module is shown in the figure, and should be interpreted as a representative for a class of algorithms (described in the text) with similar function. GD performs rapid fold determination from unassigned NMR data. NVR performs structure-based assignment. RDC-EXACT determines backbone structure de novo, from 2 RDCs per residue plus sparse NOEs. TRIANGLE assigns the NOESY spectra, allowing determination of a high-resolution monomer structure. SYMBRANE assigns intermolecular NOEs and determines the oligomeric number and complex structure. Each of these modules takes as input NMR data that can be collected in a high-throughput fashion. The major data sources are shown; complete descriptions of the data requirements are in the text. The solid arrows show the data flow for the molecular replacement-like method for NMR. Dashes show an alternative pathway for de novo assignment and structure determination in the case where a completely novel fold is detected (by GD) from unassigned NMR data. aPACES, bRGRAPH, and cJIGSAW are ab initio assignment algorithms [22, 105, 149, 70, 148, 12]. Right solid arrows show the data flow from structure to assignments. Downward arrows show the data flow from assignments to structure. dSYMBRANE simultaneously performs assignment and structure determination.

The Power of Exact Solutions

Let us consider an analogy. A point-mass pp is fired from a cannon with velocity 𝒗\mathbf{v} , where 𝒗\mathbf{v} is a tangent vector to Euclidean three-dimensional space ℝ3\mathbb{R}^3 . Assuming Newtonian dynamics, when, and where, will it hit the ground?

1 This chapter is based on our review article in Progress in Nuclear Magnetic Resonance Spectroscopy (2009).

This problem can be solved by numerical forward-integration of the dynamical equations of motion, or by random guessing (also known as Monte Carlo sampling), simulated annealing, neural networks, genetic algorithms, systematic grid search, or a host of other techniques. However, the following simple technique, from middle-school physics, suffices. The trajectory of the mass pp is given by a quadratic equation in one scalar variable (time). By solving this equation simultaneously with the plane of the ground, z=0z = 0 , the solution to our problem may be calculated exactly, in closed form, and in constant-time (using only a constant number of computer operations). In this case, “closed-form” means using only the field operations (addition, subtraction, multiplication, and division) plus calculating roots ⋅\sqrt{\cdot} . In this case, j≤2j \leq 2 .

A similar trick is available to assist in protein structure determination, (figures 16.1–16.6, plates 1, 13–15) when we have measured dipolar couplings (figure 16.5). A simplified example will be helpful to understand the idea. The example arises in protein structure determination from RDCs measured in one medium, using exact solutions.

Suppose we have recorded RDCs (figures 16.1–16.3) in a single alignment medium for NH and CαC^\alpha -H α^\alpha bond vectors (figure 16.6, plate 1), and that secondary structure regions have been identified using either chemical shifts, short-range NOEs, or scalar coupling experiments such as HNH α^\alpha or J-doubling to measure the ϕ\phi bond angles. Consider the simplified problem of computing the orientation and conformation of a secondary structure element (helix or strand) hh containing

Figure 16.1 The scalar component of the residual dipolar coupling; hh is Planck’s constant, μ0\mu_0 is the magnetic permeability of vacuum, γa\gamma_a and γb\gamma_b are the gyromagnetic ratios of two nuclei aa and bb , and θ\theta is the angle between the external magnetic field 𝑩0\mathbf{B}_0 and the internuclear vector 𝒗\mathbf{v} (from aa to bb ) in the weakly aligned anisotropic phase; ⟨3cos⁡2θ−12⟩\langle \frac{3\cos^2\theta-1}{2} \rangle is the ensemble average of the second Legendre polynomial of cos⁡θ\cos\theta ; ra,br_{a,b} is the distance between nuclei aa and bb . Here, aa and bb are assumed to be covalently bonded, and therefore the ensemble average ⟨ra,b3⟩\langle r_{a,b}^3 \rangle in the denominator is replaced with the single scalar ra,b3r_{a,b}^3 . In classical solution-state NMR, proteins tumble rapidly and isotropically and therefore the dipolar couplings average to zero. RDCs are measured by introducing a dilute alignment medium, which biases the orientational distribution of the protein so that dipolar couplings can be measured. In contrast to NOEs, whose magnitude is proportional to the interatomic distance to the inverse sixth power, RDCs are proportional to 1/ra,b31/r_{a,b}^3 . The alignment tensor 𝑺\mathbf{S} represents the molecular alignment in the anisotropic phase. It is convenient to express the residual dipolar coupling in Yan-Donald tensor notation [82, 83], as Dmax𝒗T𝑺𝒗D_{\max}\mathbf{v}^T\mathbf{S}\mathbf{v} .

Figure 16.2 (plate 13) The alignment tensor 𝑺\mathbf{S} is a symmetric second-rank tensor that may be represented by a real-valued 3×33 \times 3 matrix that is symmetric and traceless. Hence 𝑺\mathbf{S} has 5 degrees of freedom and may be decomposed using singular value decomposition (SVD) into a rotation matrix UU , called the principal order frame, and a diagonal matrix Σ\Sigma encoding its eigenvalues. The principal axes of UU encode the eigenvectors. For a fixed experimental RDC DD , the possible orientations of the corresponding internuclear vector 𝒗\mathbf{v} must lie on one of two RDC curves on the two-dimensional sphere S2S^2 . Each curve is the intersection of an ellipsoidal cone with S2S^2 . (Lower left) RDCs curves are shown spaced at 1 Hz intervals. Credit: Vincent Chen and Tony Yan.

kk residues, and that a good estimate of the alignment tensor is available. As described in several studies [152, 151, 156, 177], an initial estimate of the alignment tensor may be obtained by fitting parametric ideal helical geometry to RDCs from a secondary structure element such as a helix. The alignment tensor can be subsequently refined in an iterative fashion [152, 177].

Henceforth we will simply refer to the CαC^\alpha - HαH^\alpha bond as a CH bond, and to a CαC^\alpha - HαH^\alpha RDC as a CH RDC. Let us assume standard protein backbone geometry (figure 16.6); our example proceeds by analogy with the mathematical concept of strong induction. Assume we have already computed the structure of the first i−1<ki - 1 < k residues of hh starting at the N-terminus. In this case, the (i−1)st(i - 1)^{\text{st}} peptide plane (between residues i−1i - 1 and ii) is known (figure 16.6). As the ithi^{\text{th}} ϕ\phi dihedral angle, ϕi\phi_i rotates, the orientation of the ithi^{\text{th}} CαC^\alpha - HαH^\alpha bond vector will move in a circle (figures 16.6 and 16.7). Under any change of coordinate system, this circle will transform to an ellipse, EE , on the two-dimensional sphere S2S^2 . Such an ellipse is shown in green in figure 16.7 (plate 16).

Figure 16.3 (plate 14) It is convenient to express the internuclear vector as a unit vector of the form 𝒗\mathbf{v} , corresponding to its direction cosines. The RDC rr can be expressed in Yan-Donald tensor notation [82, 83], as r=Dmax𝒗T𝑺𝒗r = D_{\max} \mathbf{v}^T \mathbf{S} \mathbf{v} , or in a principal order frame that diagonalizes the alignment tensor, namely r=Sxxx2+Syyy2+Szzz2r = S_{xx}x^2 + S_{yy}y^2 + S_{zz}z^2 . Here, SxxS_{xx} , SyyS_{yy} and SzzS_{zz} are the three diagonal elements of a diagonalized Saupe matrix 𝑺\mathbf{S} (the alignment tensor), and xx , yy and zz are, respectively, the xx , yy , zz -components of the unit vector 𝒗\mathbf{v} in a principal order frame (POF) which diagonalizes 𝑺\mathbf{S} .

For each RDC rr , the dipolar coupling is given by the top equation in figure 16.1 (sec [140, 142]). It is convenient to express the residual dipolar coupling in Yan-Donald tensor notation [82, 83], as

r=Dmax𝒗T𝑺𝒗,(16.1)r = D_{\max} \mathbf{v}^T \mathbf{S} \mathbf{v}, \quad (16.1) where DmaxD_{\max} is the dipolar interaction constant, 𝒗\mathbf{v} is the internuclear vector orientation relative to an arbitrary substructure frame, and 𝑺\mathbf{S} is the 3×33 \times 3 Saupe order matrix [130] (figure 16.1). 𝑺\mathbf{S} is a symmetric, traceless, rank 2 tensor with 5 degrees of freedom, which describes the average substructure alignment in the weakly aligned anisotropic phase (figures 16.1 and 16.2). The measurement of five or more independent RDCs in substructures of known geometry allows determination of 𝑺\mathbf{S} [92].

Now, if the RDC has been measured for the CH bond vector in residue ii , then the RDC equation (16.1) constrains the bond vector orientation to lie on one of two curves R=R1∪R2R = R_1 \cup R_2 .

Figure 16.4 (plate 15) A cartoon of the geometry and algebra of RDCs measured in two independent aligning media. If the two principal order frames (POFs) are independent, then the internuclear unit vector 𝒗\mathbf{v} is constrained to simultaneously lie on the blue RDC curve (from the blue POF) and the red RDC curve (from the red POF). Generically, the blue and red RDC curves will intersect at 0, 2, 4, or 8 points. Here, only one of the two RDC curves is shown for each POF. Suppose that rr is the red RDC and that the diagonalized red POF can be represented as (Sxx,Syy,Szz)(S_{xx}, S_{yy}, S_{zz}) . Let u=1−2(xa)2u = 1 - 2\left(\frac{x}{a}\right)^2 , where xx is the xx -component of 𝒗\mathbf{v} and a2=(r−Szz)/(Sxx−Szz)a^2 = (r - S_{zz})/(S_{xx} - S_{zz}) ; see equation (18.5) below and [152, p. 238]. The discrete points corresponding to the RDC curve intersections are calculated exactly by solving a quartic polynomial equation in uu , of the form f4u4+f3u3+f2u2+f1u+f0=0f_4u^4 + f_3u^3 + f_2u^2 + f_1u + f_0 = 0 [152], which is also a quartic polynomial equation in x2x^2 .

Each of these curves is the intersection of S2S^2 with an ellipsoidal cone. One such curve is shown in orange in figure 16.7.

Therefore, the ϕi\phi_i angles that simultaneously satisfy protein backbone kinematics and the CH RDC data are given by the intersection of curves EE and RR , shown as the green and orange ellipses, respectively, in figure 16.7. Generically, this intersection will be a set of 0, 2, or 4 points (the 1-point solution is nongeneric), as shown in figure 16.7. Wang and Donald showed that these points are the roots of a quartic univariate polynomial equation [151, 152, 177] and hence may be computed exactly and in closed form. (Technically, we compute exact solutions for the sine and cosine of this angle ϕi\phi_i , which completely determine the angle ϕi\phi_i , which, if desired, can then be computed numerically using the 2-argument arctangent function ATAN2).

Key Ingredients

Residual dipolar couplings • Global coordinate frame

Wang-Donald equations (exact solutions to NHNH , CαC^\alpha - HαH^\alpha orientations and (ψ,ϕ)(\psi, \phi) angles):

f4u4+f3u3+f2u2+f1u+f0=0f_4u^4 + f_3u^3 + f_2u^2 + f_1u + f_0 = 0

Optimization via algebraic geometry • Conformations of secondary structure elements • Global fold

∃x*:∀x:f(x*)≤f(x)\exists x^* : \forall x : f(x^*) \leq f(x)

Figure 16.5 Key ingredients to a structure determination algorithm exploiting exact solutions and systematic search.

Figure 16.6 Protein backbone kinematics and RDC restraints. See plate 1.

Figure 16.7 (plate 16) Given NH and CαC^\alpha - HαH^\alpha RDCs measured in one medium, the Wang-Donald Structure Equations yield exact solutions for the (ϕ,ψ)(\phi, \psi) backbone dihedral angles.

Now, a solution is chosen for ϕi\phi_i from among these multiple exact solutions, and the procedure continues along the polypeptide chain. With ϕi\phi_i fixed, we find ourselves in a symmetrical situation. As the ψi\psi_i bond angle rotates, the orientation of the NH vector of residue i+1i + 1 will move in an ellipse E′E' (figure 16.7). Similarly, if the RDC has been measured for this NH bond, then its orientation will similarly be constrained to lie on curves R′R' on S2S^2 . Therefore, the orientation of the (i+1)st(i + 1)^{\text{st}} NH bond vector must lie on the intersection of the curves E′E' and R′R' , and the ψi\psi_i angles satisfying this constraint can similarly be solved for exactly and in closed form, as done previously for ϕi\phi_i .

Again, a solution is chosen for ψi\psi_i from among these multiple exact solutions, which defines the ithi^{\text{th}} peptide plane (between residues ii and i+1i + 1), and the procedure continues along the polypeptide chain. Equations describing the geometric procedure above were introduced in [151]; see [177] (Supplementary Information) for an intuitive derivation.

Every exact solution precisely satisfies the data. Since there are multiple solutions for each backbone dihedral angle a choice must be made, and this defines a discrete combinatorial search

(ϕ,ψ\phi, \psi) Angles in Conformation Tree

Figure 16.8 (plate 17) A conformation tree is a data structure used in depth-first search over the exact solutions (roots of polynomials) with backtracking or A* search, to optimally compute the backbone dihedral angles that globally best fit the RDC data and an empirical scoring function.

for the structure of the secondary structure element hh . A scoring function is used to choose the correct root, and hence the correct backbone dihedral angle. The scoring function can use the Ramachandran diagram, molecular mechanics energies, and any of the usual components of an empirical scoring function [152, 151, 156, 154, 177]. By structuring the search into a conformation tree [152, 88, 156, 45] and using a depth-first search with backtracking [152], or A* search [45], the optimal solution over the entire secondary structure element hh can be found (figure 16.8, plate 17). Henceforth, we will call such a secondary structure element hh a fragment.

The RDC RMSD term in the scoring function calculates the sum of the squared differences between the experimental RDCs and the back-computed RDCs over all kk residues of the secondary structure element hh [152]. Minimizing the scoring function over the combinatorial number of choices of the polynomial roots representing the backbone dihedral angles, will yield in the structure that optimally fits the data [152, 156, 177]. Unlike some traditional methods (SA/MD, MC, etc.) that can only compute local minima, this technique is guaranteed to compute the globally optimal solution for hh . We discuss this point next.

Computing the Globally Optimal Solution

It is important to note that the choice of backbone dihedral angle is not made locally solely using the RDC information for that residue. Rather, the scoring function includes an RDC RMSD term, so that the global optimum is computed over the entire fragment [152, 156, 177]. By global optimal we mean the minimum of the scoring function, where the minimum is taken over all (ϕ,ψ)(\phi, \psi) angles in the fragment that are zeroes of the structure equations. While a grid search over all (discretized) (ϕ,ψ)(\phi, \psi) angles is not computationally feasible, a complete search with full backtracking that considers all possible exact solutions for all possible dihedral angles is possible over secondary structure elements of up to about 20 residues [152, 156, 174, 177]. Typical scoring functions over this tree search have included terms for RDC RMSD, Ramachandran suitability, and hydrogen bonds [152, 156, 174, 177] or van der Waals packing [154], but any empirical molecular mechanics energy function would be feasible. Note that although an exhaustive search over the entire tree is theoretically necessary in the worst case, in practice, combinatorial speed-up can be obtained since, when a node is pruned, the entire subtree below it is eliminated [152, 156, 177]; (see figure 16.8).

This gives us a procedure to compute the structure of hh that optimally fits the data under the scoring function. Now, the procedure is exponential in kk , the length of hh . This exponential dependence provides a combinatorial obstruction to simply proceeding along the polypeptide chain for the entire protein. To overcome this problem, the following algorithm is used. The protein is partitioned into secondary structure regions. The orientation and conformation of each secondary structure element is solved using the techniques described earlier. Each may be solved independently and in parallel since, under suitable assumptions about the dynamics, they all share the same alignment tensor. This allows the algorithm to divide and conquer: for a protein with nn residues, there could, in principle, be at most nn secondary structure elements. However, each will have only constant length (k=O(1)k = O(1)). Therefore the problem is divided into a series of Θ(n)\Theta(n) subproblems, each of constant size. Each of these can be solved in constant time since the exponential of a constant is also a constant.

When RDCs are recorded in a single medium, there is a fourfold orientational ambiguity between a pair of secondary structure elements. This cannot be disambiguated solely using the RDCs. However, not all combinations need to be tried. The secondary structure elements can be assembled sequentially using sparse NOEs to pack them together (figure 16.9, plate 18). For example, if the secondary structure elements, whose orientations (up to the symmetry of the dipolar operator) and conformations have been optimally determined are (h1,h2,…,hm)(h_1, h_2, \dots, h_m) , then the algorithm would first pack h2h_2 to dock with h1h_1 , and then pack h3h_3 to dock with the packed substructure (h1,h2)(h_1, h_2) , and then pack h4h_4 to dock with the packed substructure (h1,h2,h3)(h_1, h_2, h_3) , and so forth. Each of these packing operations can determine the optimal packing including the orientational ambiguity. This may be done using a complete algorithm as described by several researchers [117, 152, 156, 174, 177]. Note that, although there could be Θ(n)\Theta(n) secondary structure elements, the packing and assembly problem is not exponential since it is transformed into a linear-sized sequence of constant-sized packing problems. The requirements on the NOEs

Fold via sparse NOEs

Using NOEs, find a translation* 𝒙\mathbf{x} minimizing:

∑i=1ℓ(∥ai−bi+x∥−ni)2*4-fold discreteorientationalsymmetry (1 medium)\sum_{i=1}^{\ell} (\|a_i - b_i + x\| - n_i)^2 \quad \begin{array}{l} *4\text{-fold discrete} \\ \text{orientational} \\ \text{symmetry (1 medium)} \end{array} are fairly mild since the conformation of the secondary structure elements is determined up to translation (and the fourfold discrete orientational degeneracy). This means that the translation between the oriented secondary structure elements is not mathematically determined using RDCs alone. Therefore, a small number of sparse NOEs will suffice to pack the secondary structure elements [152, 177].

Figure 16.9 (plate 18) The orientations and conformations of secondary structure elements (SSEs) can be calculated using sparse RDCs. Then the SSEs are packed using sparse NOEs. Packings are scored separately for data fit and molecular mechanics energies [117] to avoid bias. The packing by NOEs also disambiguates the discrete 4-fold orientational degeneracy due to the symmetry of the dipolar operator.

Once the global fold has been determined by packing together the secondary structure elements based on the RDCs and sparse NOEs, loops must be determined to connect them. This problem is similar to the kinematic loop closure problem in X-ray crystallography. The similarity arises because once the core structure of the secondary structure elements has been computed, it defines orientations and positions for the helices and strands. Models of loops must be built that close these kinematic gaps, to connect the secondary structure elements. The kinematic loop closure problem is combined with the RDC restraints that are measured for the loop residues, to compute an ensemble of loops that simultaneously satisfies the closed-chain kinematics and the polynomial equations arising from the RDCs [152, 174].

Finally, it is possible to model error in the input RDCs. In the simplest method, a distribution is placed over the input data, and that distribution can be sampled [152, 151]. This sampling results in a set of perturbed RDCs. The preceding combinatorially precise, exact algorithms are run for different sets of the sampled RDCs, resulting in different solutions to the structure. Out of this ensemble of solutions, the maximum-likelihood solution can be computed [152, 151, 156, 177]. Alternatively, an ensemble of structures that fit the data can be returned [154]. In the case that sampling is undesirable, it is possible, in principle, to use algebraic algorithms (polynomial arithmetic) to push the RDC error intervals through the RDC equations, and obtain a representation of the probability density function over backbone dihedral angles [156].

In general, when different RDCs (at least two) have been measured per residue, a similar algebraic and kinematic derivation holds to obtain exact solutions. The case for NH RDCs recorded in two media is shown in figure 16.4. In all cases, the coefficients of the RDC equations are determined by the data [151]. An RDC error bound therefore defines a range of coefficients, which, in turn, yield a range of roots representing the structural dihedral angles. Hence, the RDC equations define an analytical relationship between the RDC error distribution and the coordinate error of the ensemble of structures that satisfy the experimental restraints [156]. Precise methods that relate the experimental error to the coordinate error of the computed structures therefore appear within reach.

Of course, whenever exact solutions exist, there usually are also excellent numerical algorithms [37] (as opposed to exact algorithms) that stably solve the same analytical equations (18.6 and 18.9 below) not exactly, but up to the accuracy of the floating-point representation. In our motivating example of a point-mass fired from a cannon, these numerical algorithms include (for example), the eponymous Newton’s method. Such techniques, born in the field of numerical analysis and scientific computation [37], enable provably good approximation algorithms for our structure determination problem.

Limitations and Extensions

The approach described above assumes that dynamics can be neglected, although recent studies indicate that modest dynamic averaging can be tolerated, albeit with reduced accuracy in the determined orientations of internuclear bond vectors [69]. In addition, it is assumed that the alignment tensor can be estimated initially by fitting parametric secondary structure geometry (helices and β\beta -strands) to the RDCs to obtain the alignment [152], and that the alignment parameters can be optimized in an iterative fashion by alternating the roots-of-polynomials exact solutions approach to structure determination (given an alignment tensor) with fitting the alignment tensor to RDCs and the just-determined nascent partial structure (using SVD) [152, 151, 156]. While good results have generally been obtained from this methodology [152, 151, 156, 174, 177], if inaccurate tensors are used, the resulting structures may have inaccuracies [69]. We observe that the RDCs are scaled by the order parameter SS . Suppose order parameters S2S^2 are measured for the same bond vectors as the RDCs, using, for example, relaxation experiments. In this case, neglecting dynamics outside the timescale of the dynamics measurements, one may heuristically assume that when S2S^2 is sufficiently uniform (i.e., the core of the protein is largely rigid), then the dynamic averaging due to SS in the RDC measurement is safe to use for structure determination.

NMR Structure Determination Algorithms Using Sparse RDCs

Several papers [152, 151, 156, 154, 155, 174, 177] make contributions (see list on p. 146) to the method of determining protein structures by solution NMR spectroscopy using RDCs as the main restraints. These contributions may be valuable not only to the NMR community in particular and structural genomics in general, but also to structural biologists more broadly. This is because in both experimental and computational structural biology, exact computational methods have been, for the most part, elusive to date. Second, rigorous comparisons of structures derived from NMR versus X-ray crystallography are made possible by these techniques, and these comparisons should be of general interest.

One algorithm, RDC-EXACT (figure 16.5), requires the following experimental NMR data: (a) two RDCs of backbone internuclear vectors per residue (e.g., assigned NH RDCs in two media or NH and CH RDCs in a single medium); (b) identified α\alpha -helices and β\beta -sheets with known hydrogen bonds (H-bonds) between paired strands; and (c) a few NOE distance restraints. The implementation [152, 151, 156, 174, 177] uses this experimental data, and allows for missing data as well. In contrast to NOE assignment, RDCs can be recorded and assigned on the order of hours. Additionally, it is relatively straightforward to rapidly obtain the few (three or four), unambiguous NOEs required for the packing algorithm (see section 16.1) from a standard NOESY spectrum, or by using, for example, the labeling strategy of Kay and coworkers [40]. The secondary structure types of residues along the backbone can be determined by NMR from experimentally recorded scalar coupling HNHα\text{HNH}^\alpha [16, p. 524–528] data, or J-doubling [31] data for larger proteins (these experiments report on the ϕ\phi backbone angles). NMR chemical shifts [163, 165, 164, 94, 25] or automated assignment [12] can also be used. Hydrogen bonds can be determined by NMR from experimentally recorded data [24, 157], or, for example, by using backbone resonance assignment programs such as JIGSAW [12]. In the remainder of this chapter, we discuss the algorithm RDC-EXACT assuming that we are given assigned NH RDCs in two media (figure 16.4). However, the results also hold for the case of NH and CH RDCs in one medium with slight modifications to the equations in section 18.1.1 as shown in Wang and Donald [151, 177], and as illustrated in section 16.1.

Most traditional algorithms focus on using NOE restraints to determine protein structure. This approach has been shown to be NP-hard [131], essentially due to the local nature of the constraints. The most notable characteristic of NP-hard problems is that no fast solution to them is known [162]; that is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to provably solve even moderately large versions of many of these problems becomes prohibitive using any currently available amount of computing power. Here, this implies that no algorithm for computing a structure that globally satisfies a dense network of NOE constraints can be mathematically proven to produce a satisfactory solution in a reasonable time. This is an undesirable property for structure determination software. In particular, in the case of algorithms such as SA/MD and Monte Carlo, no guarantees of soundness, efficiency, or completeness can be made. In contrast, it is remarkable that by primarily using RDCs instead of NOEs, provably polynomial-time algorithms can be obtained that have guarantees of soundness, efficiency, and completeness.

In practice, approaches such as molecular dynamics and simulated annealing [15, 52], which lack both combinatorial precision and guarantees on running time and solution quality, are used routinely for structure determination. Several structure determination approaches do use RDCs, along with other experimental restraints such as chemical shifts or sparse NOEs [6, 32, 46, 62, 125, 139], yet remain heuristic in nature, without guarantees on solution quality or running time. Unlike previous approaches ([14] is a notable exception), which have either no theoretical guarantees [15, 52, 6, 32, 46, 62, 125, 139], or run in worst-case exponential time [131, 29, 28, 55, 56], recent methodology has shown that it is possible to exploit RDC data, which gives global restraints on the orientation of internuclear bond vectors, in conjunction with very sparse NOE data, to obtain an algorithm that runs in polynomial time and provably computes the structure that agrees best with the experimental data.

These results are consistent with earlier observations [140, 1, 139, 38, 120, 6, 32, 46, 62, 125, 159] that, empirically, RDCs increase the speed and accuracy of biomacromolecular structure determination: RDC-EXACT formally quantifies the complexity-theoretic benefits of employing globally referenced angular data on internuclear bond vectors. The main contributions of this work were as follows:

  1. To derive low-degree polynomial equations that can be solved exactly and in constant time, to determine backbone (ϕ\phi , ψ\psi) angles from experimentally recorded RDCs. Only two RDCs per residue are required. For example, after measuring RDCs corresponding to a single internuclear vector 𝒗\mathbf{v} in two different aligning media, the easily-computable exact solutions eliminate the need for one-dimensional grid search previously employed [159] to compute the direction of 𝒗\mathbf{v} or two-dimensional grid search [46, 139, 158, 93] to compute (ϕ\phi , ψ\psi) angles. The main results also hold for the case of NH and CH RDCs in one medium with slight modifications to the Wang-Donald equations in section 18.1.1, as shown in several studies [151, 156, 174, 177] (see section 16.1). Furthermore, these equations are very general and can be extended to compute other backbone and side-chain dihedral angles. The method can be applied mutatis mutandis to derive similar equations for computing dihedral angles from RDCs in nucleic acids.
  2. The first NMR structure determination algorithm that simultaneously uses exact solutions, systematic search, and only two RDCs per residue. (A systematic search is a search over all possible conformations (solutions) that employs a provable pruning strategy that guarantees pruned conformations need not be considered further).
  3. The first combinatorially precise, polynomial-time algorithm for structure determination using RDCs, secondary structure type, and very sparse NOEs.
  4. The first provably polynomial-time algorithm for de novo backbone protein structure determination solely from experimental data (of any kind).

Table 17.1 Results of RDC-EXACT

Protein a α/β\alpha/\beta
residues b
RDCs c Type of
RDCs d
Hydrogen
bonds e
NOEs f RMSD g
Ubiquitin 39/75 78 NH in two media 12 4 1.23 Å
Ubiquitin 41/75 76 NH, CH in one medium 12 4 0.97 Å
Dini 41/81 75 NH in two media 6 9 1.55 Å
Dini 41/81 80 NH, C α C f in one medium 6 9 1.35 Å
Protein G 29/56 53 NH in two media 9 4 0.98 Å
Protein G 33/56 61 NH, C α C f in one medium 9 4 1.30 Å
  1. experimental RDC data for ubiquitin (PDB ID: 1D3Z), Dini (PDB ID: 1GHH), and Protein G (PDB ID: 3GB1) were taken from the Protein Data Bank (PDB). (b) Number of residues in α\alpha -helices or β\beta -sheets, versus the total number of residues. (c) The total number of experimental RDCs (note that RDCs are missing for some residues). (d) RDCs from different experimental datasets (for different bond vectors) were used. (e) Number of hydrogen bonds used. (f) Number of NOEs used. (g) RMSD (for Cα, N, and Cf backbone atoms) between the oriented and translated secondary structure elements (excluding loop regions) computed by RDC-EXACT to reference structures: ubiquitin to a high-resolution X-ray structure (PDB ID: 1UBQ); Dini to an NMR structure (PDB ID: 1GHH); and Protein G to an NMR structure (PDB ID: 3GB1).
  1. An implementation of the algorithm that is competitive in terms of empirical accuracy and speed, but requires much less data than, previous NMR structure determination techniques.

  2. Testing and results of the algorithm on protein NMR data.

Representative results from RDC-EXACT, including RMSD to high-resolution crystal structures and NMR structures, are shown in table 17.1 and figure 17.1 (plate 19). In addition to these studies several blind tests of RDC-EXACT were performed, in which the structure was not known ahead of time [174]. NMR data were recorded for the ubiquitin-binding zinc finger domain of the human DNA Y-polymerase eta (pol η\eta). Zeng et al. [174] used NH and Hα-Cα RDCs recorded in one medium, with typically 10–15% missing data (but up to 32%) in one secondary structure region, plus 9 NOEs between the helix and β\beta -strands. The structure of pol η\eta was then computed by RDC-EXACT, and is shown in figure 17.2L (plate 20). The RDC-EXACT structure [174, 177] was compared with the structure being determined (by conventional techniques) in Pei Zhou’s laboratory (figure 17.2C). The core structure (helix and sheet) computed by RDC-EXACT was 1.28 Å RMSD from the Zhou lab structure (figure 17.2C). In a second test, the same suite of NMR data [174, 177] was obtained for a second protein, the human Set2-Rpb1 interacting (SRI) domain. The global fold of human SRI was determined by RDC-EXACT, similarly using NH and Hα-Cα RDCs recorded in one medium, plus sparse NOEs. The resulting core structure (a 3-helix bundle) had an RMSD of 1.61 Å to the reference structure (see figure 17.2R). Both reference structures were determined using traditional methods (XPLOR [15]) requiring a much larger set of experimental spectra. The accuracy of RDC-EXACT on these blind tests is comparable to the accuracy achieved in the retrospective studies (figure 17.1 and table 17.1). The ability of RDC-EXACT to determine the global fold of pol η\eta and human SRI with reasonable accuracy,

Reference a Program Technique b Restraints per Residue c Accuracy d
Brown Lab [46] X-plor MD/SA 6 RDCs 1.45 Å
Blackledge Lab [62] SCULPTOR MD/SA 11 RDCs, 1.00 Å
Bax Lab [32] MFR Database 10 RDCs, 5 Chemical shifts 1.21 Å
Baker Lab [125] RosettaNMR DataBase/MC 3 RDCs, 5 Chemical shifts 1.65 Å
Baker Lab [125] RosettaNMR DataBase/MC 1 RDC 2.75 Å
Donald Lab e RDC-EXACT Exact equations 2 RDCs 1.45 Å

Figure 17.1 (plate 19) Top: Structure of ubiquitin backbone with loops. The ubiquitin backbone structure (blue) was computed by extending rdc-EXACT to handle loop regions along the protein backbone [156]. The structure was computed using 59 NH and 58 CH RDCs (117 out of 137 possible RDCs; 20 are missing), 12 H-bonds, and 2 unambiguous NOEs. The structure has a backbone RMSD of 1.45 Å with the high-resolution X-ray structure (PDB ID: 1UBQ, in magenta) [147]. Bottom: Comparison of rdc-EXACT with previous approaches. (a) References to previously computed ubiquitin backbone structures (including loop regions), (b) algorithmic technique; (c) data requirements; (d) backbone RMSD of structure (for Cα, N, and C’ backbone atoms) compared to the X-ray structure (1UBQ). The structure computed by rdc-EXACT includes loops and turns, as shown at top. eReferences [152, 151, 156, 155].

using only a minimal suite of experiments, that could be collected in a high-throughput fashion, supports the feasibility of the exact solutions approach for structure determination.

  1. rdc-EXACT can compute β\beta -sheets from RDC data alone, which fundamentally extends previous methods [38] targeting only entirely helical proteins. Unlike α\alpha -helices, β\beta -strands are often twisted in globular proteins so it is important to refine them accurately from RDC data. rdc-EXACT can determine the backbone structures of proteins consisting of either α\alpha -helices, β\beta -sheets, or both, and thus has wider application since most proteins have both α\alpha -helices and β\beta -sheets.

  2. rdc-EXACT was the first demonstration that the conformations and orientations of both α\alpha -helices and β\beta -strands can be computed accurately and efficiently using exclusively RDCs measured on a single bond vector type (NH) in only two aligning media [152]. Similar accuracies and efficiency were obtained using only NH and CH RDCs in one medium [151, 156, 174, 177].

Figure 17.2 (plate 20) Left: The global fold of polη\text{pol}\eta , computed by RDC-EXACT using 2 RDCs per residue measured in one medium plus 9 NOEs between the helix and β\beta -strands. Center: Comparison of polη\text{pol}\eta to the reference structure, PDB id: 215O. The RMSD of the secondary structure elements is 1.28 Å. Right: Global fold of human SRI, computed by RDC-EXACT (thick lines) using two RDCs per residue measured in one medium plus sparse NOEs. The reference structure is shown in thin lines (PDB id: 2A7O [86]).

With a minimum number of additional distance restraints a three-dimensional structure could be computed consequently [152, 156, 174, 177].

Structure determination using sparse data is an underconstrained problem. Additional constraint may be obtained using structure prediction [73, 126] or homology modeling [121]. The former reduces to decoy detection, pruned by NMR data. The second reduces to biasing the structure determination using the PDB. In both approaches, sparse RDCs can be employed, but, compared with conventional protocols, the resulting structures obtain their authority less from the data and more from modeling or homology. In contrast, the exact solutions technique admits algorithms that can extract more structural information from less NMR data, than had been previously exploited. This can be done using a combination of computer algebra, computational geometry, and statistical methods. Compared with previous algorithms for computing backbone structures using RDCs, RDC-EXACT achieves similar accuracies but requires less data, relies less on statistics from the PDB and does not depend on molecular dynamics or simulated annealing (figures 17.1 and 17.2; table 17.1). Since RDCs can be acquired and assigned much more quickly than NOEs in general, the results show it is possible to compute structures rapidly and inexpensively using mainly RDC restraints.

Nuclear Vector Replacement for Automated NMR Assignment and Structure Determination

High-throughput NMR structural biology can play an important role in structural genomics. Recent results have generalized and extended structure-based assignment algorithms such as

Figure 17.3 Nuclear vector replacement. Left: Schematic of the NVR algorithm for resonance assignment using EM. The NVR algorithm takes as input a model of the target protein and several unassigned spectra, including the 15N^{15}\text{N} -HSQC, HN\text{H}^{\text{N}} - 15N^{15}\text{N} RDC, 15N^{15}\text{N} -HSQC-NOESY, and an H-D exchange-HSQC to measure amide exchange rates. In the first phase, NVR computes the alignment tensors for both media using chemical shift prediction, dNNSd_{\text{NNS}} , H-D exchange-exchange rates and the EM algorithm. This step takes time O(n2)O(n^2) , where nn is the number of residues. In the second phase, chemical shift predictions, dNNSd_{\text{NNS}} , RDCs in two media and the EM algorithm are used to assign all remaining peaks. This entire process runs in minutes, and is guaranteed to converge in time O(n3)O(n^3) . NVR Experiment Suite: Right: The 5 unassigned NMR spectra used by NVR to perform resonance assignment. The HSQC provides the backbone resonances to be assigned. HN\text{H}^{\text{N}} - 15N^{15}\text{N} RDC data in two media provide independent, global restraints on the orientation of each backbone amide bond vector. The H-D exchange HSQC identifies fast-exchanging amide protons. These amide protons are likely to be solvent-exposed and non-hydrogen-bonded and can be correlated to the structural model. A sparse number of unambiguous, unassigned dNNSd_{\text{NNS}} can be obtained from the NOESY. These dNNSd_{\text{NNS}} provide distance constraints between spin systems which can be correlated to the structural model. Chemical shift predictions are used as a probabilistic constraint on assignment.

JIGSAW [12], to obtain an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of an homologous structure [79, 82, 83, 78, 8]. Nuclear vector replacement (NVR) uses expectation/maximization (EM) to compute assignments (figure 17.3L). NVR is an RDC-based algorithm, which computes assignments that correlate experimentally measured RDCs, chemical shifts, HN\text{H}^{\text{N}} - HN\text{H}^{\text{N}} NOEs (which are called dNNSd_{\text{NNS}}) and amide exchange rates to a given priori 3D backbone structural model. The algorithm requires only uniform 15N^{15}\text{N} -labeling of the protein, and processes unassigned HN\text{H}^{\text{N}} - 15N^{15}\text{N} HSQC spectra, HN\text{H}^{\text{N}} - 15N^{15}\text{N} RDCs, and sparse dNNSd_{\text{NNS}} , all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments (figure 17.3R). NVR could form the basis for “Molecular Replacement (MR) by NMR.” RDCs provide global orientational restraints on internuclear bond vectors (see equation 16.1 and figures 16.1 and 16.2). Once the alignment tensor 𝑺\mathbf{S} has been determined, RDCs may be simulated (back-calculated) given any other internuclear vector 𝒗i\mathbf{v}_i . In particular, suppose an (HN,15N)(\text{H}^N, {}^{15}\text{N}) peak ii in an HN−15N\text{H}^N-{}^{15}\text{N} HSQC (subsequently termed simply “HSQC”) spectrum is assigned to residue jj of a protein, whose crystal structure is known. Let rir_i be the measured RDC value corresponding to this peak. Then the RDC rir_i is assigned to amide bond vector 𝒗j\mathbf{v}_j of a known structure, and we should expect that ri≈Dmax𝒗jT𝑺𝒗jr_i \approx D_{\max} \mathbf{v}_j^T \mathbf{S} \mathbf{v}_j (although noise, dynamics, crystal contacts in the structural model, and other experimental factors will cause deviations from this ideal).

SBA approaches use unassigned NMR data, such as RDCs. Note that, in contrast, assigned RDCs have also been employed by a variety of structure refinement [19] and structure determination methods [62, 6, 159], including orientation and placement of secondary structure to determine protein folds [38], pruning an homologous structural database [7, 96], de novo structure determination [125], in combination with a sparse set of assigned NOEs to determine the global fold [100], and a method for fold determination that selects heptapeptide database fragments best fitting the assigned RDC data [32]. Bax and coworkers termed their technique “molecular fragment replacement” [32], by analogy with X-ray crystallography MR techniques. Unassigned RDCs have been successfully used to expedite resonance assignments [176, 32, 139].

The idea of correlating unassigned experimentally measured RDCs with bond vector orientations from a known structure was first proposed by Al-Hashimi and Patel [4] and subsequently demonstrated by Al-Hashimi et al. [3] who considered permutations of assignments for RNA, and also in reference [63]. Brüschweiler and coworkers [63] successfully applied RDC-based maximum bipartite matching to structure-based resonance assignment. Their technique requires RDCs from several different bond types which, in turn, requires 13C{}^{13}\text{C} -labeling of the protein and triple resonance experiments. NVR builds on these works and offers some improvements in terms of isotopic labeling, spectrometer time, accuracy, and computational complexity. NVR algorithms have addressed the following hypothesis: Are backbone amide RDCs and dNNSd_{\text{NNS}} sufficient for performing resonance assignment? Like the techniques of Hus et al. [63], NVR calls optimal bipartite matching as a subroutine, but within an Expectation/Maximization (EM) framework that offers some benefits, described later. Previous methods (and later algorithms [67, 64]) required 13C{}^{13}\text{C} -labeling and RDCs from many different internuclear vectors (for example, C′−15N\text{C}'-{}^{15}\text{N} , C′−HN\text{C}'-\text{H}^N , Cα−Hα\text{C}^\alpha-\text{H}^\alpha , etc.). NVR uses a different algorithm and requires only amide bond vector RDCs, no triple-resonance experiments, and no 13C{}^{13}\text{C} -labeling. Moreover, NVR is more efficient. The combinatorial complexity of the assignment problem is a function of the number nn of residues (or bases in a nucleic acid) to be assigned, and, if a rotation search is required, the resolution k3k^3 of a rotation-space grid over the Lie group SO(3)SO(3) of 3D rotations. The time-complexity of the RNA-assignment method, named CAP [3], grows exponentially with nn . In particular, CAP performs an exhaustive search over all permutations, making it difficult to scale up to larger RNAs. The method presented in Hus et al. [63] runs in time O(In3)O(In^3) , where O(n3)O(n^3) is the complexity of bipartite matching [76] and II is the number of times that the bipartite matching algorithm is called. II may be bounded by O(k3)O(k^3) , the time to search for the principal order frame (POF) over SO(3)SO(3) . Thus, the full time-complexity of the algorithm presented in Hus et al. [63] is O(k3n3)O(k^3n^3) . Version 1.0 of NVR [82, 83, 78] also performed a discrete grid search for the POF over SO(3)SO(3) , but used a more efficient algorithm with time-complexity O(nk3)O(nk^3) . Once the POF has been computed, resonance assignments are made in time O(n3)O(n^3) . Thus, the total running time of NVR Version 1.0 [82, 83] is less: O(nk3+n3)O(nk^3 + n^3) . Zweckstetter and Bax [175] estimated alignment tensors (but not assignments) using permutations of assignments on a subset of the residues identified using either selective labeling or 13Cα/β^{13}\text{C}^{\alpha/\beta} chemical shifts. If mm residues can be thus identified a priori, then this method provides an O(nm6)O(nm^6) tensor estimation algorithm that searches over all possible assignment permutations.

NVR Version 2.0 [79] requires neither a search over assignment permutations, nor an explicit rotation search over SO(3)SO(3) . Rather, EM [33] is used to correlate the chemical shifts of the 15N^{15}\text{N} - 15N^{15}\text{N} HSQC resonance peaks with the structural model. In practice, the application of EM on the chemical shift data is sufficient to uniquely assign a small number of resonance peaks, and directly determine the alignment tensor by singular value decomposition (SVD) (see figure 16.2). NVR 2.0 eliminates the rotation grid-search over SO(3)SO(3) , and hence any complexity dependence on a grid or its resolution kk , running in O(n3)O(n^3) time, scaling easily to proteins in the middle NMR size range (n=56n = 56 to 129 residues) [79]. Moreover, NVR elegantly handles missing data (both resonances and RDCs).

NVR adopts a sparse-data, or minimalist approach [12], demonstrating the large amount of information available in a few key spectra. By eliminating the need for triple resonance

Table 17.2 Backbone Amide Resonance Assignment Accuracy using NVR

PDB ID a Accuracy b PDB ID a Accuracy b
1G6J [10] 100% 1GB1 [50] 100%
1UBI [123] 100% 2GB1 [50] 96%
1UBQ [147] 100% 1PGB [39] 100%
1UD7 [66] 100%
(i) Ubiquitin (ii) SPG
PDB ID a Accuracy b PDB ID a Accuracy b
193L [146] 100% 1LYZ [35] 100%
1AKI [9] 100% 2LYZ [35] 100%
1AZF [90] 100% 3LYZ [35] 100%
1BGI [106] 100% 4LYZ [35] 100%
1H87 [47] 100% 5LYZ [35] 100%
1LSC [77] 100% 6LYZ [35] 100%
1LSE [77] 100%
(iii) Lysozyme (iv) Lysozyme

Accuracies report the percentage of correctly assigned backbone HSQC peaks. aStructural model used. bAccuracy of NVR on the NMR data shown in figure 17.3 R for ubiquitin (i), SPG (ii), and lysozyme (iii-iv). The 96% accuracy for 2GB1 reflects a single incorrect assignment.

experiments, NVR saves spectrometer time. The required data (figure 17.3R) can be acquired in about one day of spectrometer time using a cryoprobe. NVR runs in minutes and efficiently assigns the (HN,15NH^N, {}^{15}N) backbone resonances as well as the sparse dNNd_{NN} s from the 3D 15N{}^{15}N -NOESY spectrum. NVR was tested on NMR data from 3 proteins using 20 different alternative structures, all determined either by X-ray crystallography or by different NMR experiments (without RDCs) (table 17.2). When NVR was run on NMR data from the 76-residue protein, human ubiquitin (matched to four structures, including one mutant/homolog), it achieved 100% assignment accuracy. Similarly good results were obtained in experiments with the 56-residue streptococcal protein G (SPG) (99%) and the 129-residue hen lysozyme (100%) when they were matched by NVR to 16 3D structural models. Table 17.1 summarizes the performance of NVR using alternative structures of ubiquitin, SPG, and lysozyme, none of which were refined using RDCs. 1UD7 is a mutant form of ubiquitin where 7 hydrophobic core residues have been altered (I3V, V5L, I13V, L15V, I23F, V26F, L67I). It was chosen to test the effectiveness of NVR when the model is a (close) homolog of the target protein. This success in assigning the mutant 1UD7, suggests that NVR could be applied more broadly to assign spectra based on homologous structures [79, 8]. Thus, NVR could play a role in structural genomics.

Protein Fold Determination via Unassigned Residual Dipolar Couplings

Sequence homology can be used to predict the fold of a protein, yielding important clues as to its function. However, it is possible for two dissimilar amino acid sequences to fold to the “same” tertiary structure. For example, the RMSD between the human ubiquitin structure (PDB Id: 1D3Z) and the structure of the Ubx domain from human Fas-associated factor 1 (Faf1; PDB Id: 1H8C) is quite small (1.9 Å), yet they have only 16% sequence identity. Detecting structural homology given low sequence identity poses a difficult challenge for sequence-based homology predictors. Is there a set of fast, cheap experiments that can be analyzed to rapidly compute 3D structural homology? A new method for homology detection has been developed, called gd, that exploits high-throughput solution-state NMR. This algorithm extends the NVR technique to perform protein 3D structural homology detection, demonstrating that NVR and its generalization gd, are able to identify structural homologies between remote amino acid sequences from a database of structural models. The first paper on protein fold determination using unassigned RDCs was published in RECOMB in April 2003 [82]. Other papers on this topic include [78] and [83, 80]. One goal of structural genomics is the identification of new protein folds. gd is an automated procedure for detecting 3D structural homologies from sparse, unassigned protein NMR data, and could aid in prioritizing unknown proteins for structure determination. gd identifies the 3D structural models in a protein structural database whose “unassigned geometries” best fit the unassigned experimental NMR data. It does not use sequence information and is thus not limited by sequence homology. gd can also be used to confirm or refute structural predictions made by other techniques such as protein threading or sequence homology.

U Homolog (native) Sequence Identity (%) RMSD (Å) Rank a
(1D3Z) 100 0 1
1NDD 55.6 0.6 2
1BT0 61.0 0.7 3
1H8C b 15.7 1.9 11
1GUA 11.6 2.1 19
1C1Y 11.6 2.1 38
L Homolog (native) Sequence Identity (%) RMSD (Å) Rank a
(1E8L) 100 0 1
2EQL 49.2 1.8 2
1ALC 35.8 1.8 3
1HFZ 38.3 1.8 4
1A4V 38.2 1.8 5
1F6S 38.7 1.7 6

Figure 17.4 GD, Representative results. GD was tested on unassigned HN-15N RDCs for 5 proteins [78]; representative scatter plots of RMSD vs. the score computed by GD are shown for human ubiquitin (top left) and hen lysozyme (top right). Only proteins within 10% of the target protein’s length are plotted. Circles are data points for the native structure (1D3Z for ubiquitin; 1E8L for lysozyme) and five homologous structures (tables U and L). The + signs are the data points associated with nonhomologous proteins. The diamond is the 2D mean of the +’s while the triangle is the 2D mean of the circles. The trend line shows the correlation between the score computed by GD and RMSD for all the data points. The scores associated with the native fold and the 5 homologs are statistically significantly lower than the scores of unrelated proteins ( pp -values <2.7×10−5< 2.7 \times 10^{-5} ). Tables: GD results for (U) ubiquitin and (L) lysozyme. The sequence identity and RMSD of these 2 test proteins with their respective top 5 homologs are shown. aThe rank of each model, out of 2,456 proteins in the database, using the score computed by GD. bThe Ubx domain from human Faf1 (see section 17.3) was ranked 11th.

GD runs in O(pnk3)O(pnk^3) time, where pp is the number of proteins in the database (2,456 in [82, 78, 83]), nn is the number of residues in the target protein, and kk is the resolution of a rotation search. GD requires only uniform 15N^{15}\text{N} -labeling of the protein and processes unassigned HN−15N\text{H}^{\text{N}-^{15}\text{N}} RDCs, which can be acquired rapidly. Experiments on NMR data from 5 different proteins demonstrated that GD identifies closely related protein folds, despite low-sequence homology between the target protein and the computed model [82, 78, 83, 80]. The overall rankings of the top predicted homologs are good (figure 17.4). Human Faf1 (1H8C) (discussed earlier) was identified as a structural homolog of ubiquitin (figure 17.4U). GD does best on lysozyme, where the native structure and 5 homologous structures occupied the top 6 places (figure 17.4L).

GD [82] represented the first systematic algorithm to exploit an unassigned “fingerprint” of RDCs for rapid protein fold determination. After Langmead et al. [82], a similar idea was independently proposed and extended by number of researchers including Prestegard [145, 128], Baker [97], [98], and coworkers. GD was later extended to demonstrate high-throughput inference of protein-protein interfaces using only unassigned NMR data [99], which should be valuable in structural proteomics.

Automated NOE Assignment Using a Rotamer Library Ensemble and RDCs

Despite recent advances in RDC-based structure determination (see sections 16.1–17.1), NOE distance restraints are still important for computing a complete three-dimensional solution structure including side-chain conformations. In general, NOE restraints must be assigned before they can be used in a structure determination program. NOE assignment is very time-consuming to do manually, challenging to fully automate, and has become a key bottleneck for high-throughput NMR structure determination. The difficulty in automated NOE assignment is ambiguity: there can be tens of possible different assignments for an NOE peak based solely on its chemical shifts. Most automated NOE assignment approaches [103, 57, 59, 68, 60, 53, 91] rely on an ensemble of structures, computed from a subset of all the NOEs, to iteratively filter ambiguous assignments. Despite this progress, there is room for improvement since previous methods require quite high-quality input data. For example, they typically require initializing the assignment/structure determination/assignment cycle with a large number of unambiguous or manually assigned NOE peaks (e.g., >5>5 NOEs per residue in [103]), >85%> 85\% complete resonance assignments (including side-chains), almost complete aromatic side-chain assignments, a low percentage of noise peaks, and only small errors in chemical shifts (≤0.03\leq 0.03 ppm for 3D NOESY spectra). Moreover, previous algorithms are heuristic in nature, provide no guarantees on solution quality or running time, and consume many hours to weeks of computation time.

Sparse dipolar couplings have enabled the development of new NOE assignment algorithms, including TRIANGLE [153] and HANA [174, 177]. An in-depth understanding of HANA [177] would require a review of the minimum Hausdorff distance [37] and Chernoff tail bounds [174], which are beyond the scope of this book. Therefore, we describe the conceptually simpler TRIANGLE algorithm; since the information content of the input data is identical, TRIANGLE will illustrate the basic paradigm. The interested reader can consult Zeng et al. [177] for a description of HANA, which extends TRIANGLE and is more general and robust. TRIANGLE begins with known resonance assignments and an accurate backbone structure computed using RDC-EXACT (sections 16.1–17.1; [152, 151, 156]). In principle, another structure determination algorithm could be used instead. However, RDC-EXACT is the only algorithm that can compute a complete protein backbone structure de novo using only two RDCs per residue. TRIANGLE uses the backbone structure determined by RDC-EXACT to bootstrap the automated assignment of NOEs: the assignment proceeds by filtering the experimentally measured NOEs based on consistency with the backbone structure.

One novel feature of TRIANGLE is the use of a rotamer-library-derived ensemble of intraresidue vectors between the backbone atoms and side-chain protons to reduce the ambiguity in the assignment of NOE restraints involving side-chain protons, especially aliphatic protons. The rotamer database was built from ultra-high-resolution structures (<1.0 Å<1.0\text{ \AA}) in the PDB [153]. TRIANGLE merges this ensemble of intraresidue vectors, together with internuclear vectors from the computed backbone structure. For example, consider the putative assignment of an NOE to an (HN,Hδ)(\text{H}^N, \text{H}^\delta) pair of protons. The triangle relationship (figure 17.5L, plate 21) defines a decision procedure to filter NOE assignments by fusing information from RDCs (𝒗Nβ\mathbf{v}_{N\beta}), rotamer modeling (𝒗βδ\mathbf{v}_{\beta\delta}), and NOEs (|𝒗Nδ||\mathbf{v}_{N\delta}|). More details of the TRIANGLE algorithm are provided in other studies [153, 174] and section 18.1.3.

Figure 17.5 (plate 21) Left: The triangle relationship, defines a decision procedure to filter NOE assignments by fusing information from structure ( 𝒗Nβ\mathbf{v}_{N\beta} ), modeling ( 𝒗βδ\mathbf{v}_{\beta\delta} ), and experiment ( |𝒗Nδ||\mathbf{v}_{N\delta}| ). An accurate backbone structure is first computed using only 2 RDCs per residue (section 17.1). The vector 𝒗Nβ\mathbf{v}_{N\beta} is computed from this backbone structure. 𝒗βδ\mathbf{v}_{\beta\delta} is a rotamer ensemble-based intraresidue vector mined from the PDB. The computed length of 𝒗Nδ\mathbf{v}_{N\delta} is compared with the experimental NOE distance dNd_N (measured using NOE cross-peak intensities) to filter ambiguous NOE assignments. The complexity of NOE assignment is O(n2log⁡n)O(n^2 \log n) , where nn is the number of protons in the protein. One cycle of NOE assignment suffices when a well-defined backbone structure is computed using RDC-EXACT. In practice, it took less than one second to assign 1,783 NOE restraints from the NOE peak list picked from both the 3D 15N^{15}\text{N} -edited and 13C^{13}\text{C} -edited NOESY spectra of human ubiquitin. Right and center: The NMR structures computed from the automatically assigned NOEs. The middle panel shows the 12 best NMR structures with no NOE distance violation larger than 0.5 Å. The side-chains are blue; the backbone is magenta. The right panel is the overlay of the NMR average structure (blue) with the 1.8 Å X-ray structure (magenta) [147].

Table 17.3 NOE restraints automatically assigned by TRIANGLE

Spectrum No. of Peaks No. of Assigned NOEs No. of Sequential NOEs (a) No. of Medium (b) , long-range NOEs (c)
15 N-NOESY 1,083 1,288 822 466
13 C-NOESY 420 495 228 167
  1. NOEs between residue ii and i+1i + 1 , (b) NOEs between residue ii and i+ji + j where 1<j<41 < j < 4 , and (c) NOEs between residue ii and i+ji + j where j≥4j \geq 4 . No., number.

In Wang and Donald [153], RDC-EXACT was first employed to compute an accurate backbone structure of ubiquitin using only two backbone RDCs per residue (figure 17.1L; [152, 151, 156]). Next, TRIANGLE was successfully applied to assign more than 1,700 NOEs, with better than 90% accuracy on the experimental 15N-and 13C-edited 3D NOESY spectra for ubiquitin [153]. The result of the automated assignment is summarized in table 17.3. Out of the 1,153 NOE peaks picked from the 15N-edited NOESY spectrum, 1,083 originate from backbone amide protons, and the remaining 50 are from side-chain amide protons. Only 420 NOE peaks originating from backbone H α\alpha protons could be picked from the 13C-edited NOESY spectrum. TRIANGLE was able to assign 1,053 NOE peaks from the 1,083 peaks picked from 15N-edited NOESY spectrum and 393 peaks from the 420 peaks picked from 13C-edited NOESY spectrum. The assigned NOE distance restraints are divided into two classes: sequential NOEs and medium/long-range NOEs (table 17.3). The number of assigned NOE distance restraints is larger than the number of assigned peaks since it is possible that more than one NOE restraint could be assigned to a single peak. It took less than one second on a 2.4-GHz single-processor Linux workstation for TRIANGLE to compute the assignments.

To test the quality of the 1,783 NOE restraints automatically generated and assigned by TRIANGLE (table 17.3), Wang and Donald [153] then used these restraints to calculate the structure of ubiquitin, using a hybrid distance-geometry and SA protocol (XPLOR [15]). No RDC restraints were used. In the resulting ensemble of 70 structures, 163 restraints had NOE violations larger than 0.5 Å in 50 structures. However, none of the NOE violations was larger than 2.5 Å. After these 163 restraints were deleted from the NOE list, XPLOR was invoked for a second time to compute the structures using the remaining 1,620 NOE restraints. Twelve structures out of 70 total computed structures had no NOE violations larger than 0.5 Å. Thus, the NOE assignment algorithm had an accuracy of 91%, and the incorrect assignments could easily be detected and removed. The 12 best NMR structures (figure 17.5C) can be overlayed with a pairwise RMSD of 1.18±0.161.18 \pm 0.16 Å for backbone atoms and a pairwise RMSD of 1.84±0.191.84 \pm 0.19 Å for all heavy atoms. The accuracy of the structures computed using the automatically assigned NOEs from TRIANGLE is in the range of typical high-to medium-resolution NMR structures. The average structure (figure 17.5R) computed from the best 12 structures has a 1.431.43 Å backbone RMSD and 2.132.13 Å all heavy-atom RMSD from the 1.81.8 Å ubiquitin X-ray structure [147]. HANA, a successor to TRIANGLE, was tested on additional proteins, resulting in similarly good accuracies [174, 177].

RDC-EXACT and HANA were used prospectively to determine the NMR solution structure of the FF Domain 2 of human transcription elongation factor CA150 (RNA polymerase II C-terminal domain interacting protein), PDB id: 2kiq [177], and a number of algorithmic enhancements and retrospective validation tests of these software modules have been described [177].

NMR Structure Determination of Symmetric Homo-Oligomers

Symmetric homo-oligomers play pivotal roles in complex biological processes including ion transport and regulation, signal transduction, and transcriptional regulation. RDCs were recently used in studies of phospholamban, a symmetric homopentameric membrane protein that regulates the calcium levels between cytoplasm and sarcoplasmic reticulum and hence aids in muscle contraction and relaxation [111]. Ion conductance studies [75] also suggest that phospholamban might have a separate role as an ion channel. To understand the dual function of phospholamban and other such symmetric homo-oligomers, a combined experimental-computational approach, SYMBRANE [117, 118], determined their structures using sparse intersubunit NOE distance restraints and van der Waals (vdW) packing. In this case, the RDCs were used to refine the subunit structure.

SYMBRANE is complete in that it tests all possible conformations, and it is data-driven in that it first tests conformations for consistency with data and only then evaluates each of the consistent conformations for vdW packing. Completeness in a structure determination method is a key requirement since it ensures that no conformation consistent with the data is missed. This avoids any bias in the search, as well as any potential for becoming trapped in local minima, problems inherent in energy minimization–based approaches. (RDC-EXACT, described above in sections 16.1–17.1, is also complete.) The data-driven nature of SYMBRANE allows one to independently quantify the amount of structural constraint provided by data alone, versus both data and packing. This avoids overreliance on subjective choices of parameters for energy minimization, and consequent false precision in determined structures. Analogously to single particle analysis in cryoelectron microscopy [107], SYMBRANE also allows determination of the oligomeric number of the complex. SYMBRANE was the first approach that determines the oligomeric number of a symmetric homo-oligomer from intersubunit NOE distance restraints. The complete ensemble of NMR structures of the human cardiac phospholamban pentamer, determined by SYMBRANE, was reported by Potluri et al. [117] and deposited in the PDB (id: 2HYN).

SYMBRANE exploits the observation that, given the structure of a subunit, the structure of a symmetric homo-oligomer is completely determined by the parameters (position and orientation) of its symmetry axis. Thus, we can formulate structure determination as a search in the space of all symmetry axis parameters, symmetry configuration space (SCS). SYMBRANE performs a branch-and-bound search in the SCS, which defines all possible CnC_n homo-oligomeric complexes for a given subunit structure. It eliminates those symmetry axes inconsistent with NOE distance restraints and then identifies conformations representing any consistent, well-packed structure.

SYMBRANE consists of two phases. The first phase performs a complete, data-driven search in SCS and returns consistent regions in SCS, that is, regions representing all conformations consistent with (i.e., satisfying) the data. In the second phase, all satisfying structures are evaluated for vdW packing. SYMBRANE computes a set of well-packed satisfying (WPS) structures that are not only consistent with data, but also have high-quality vdW packing. SYMBRANE explicitly quantifies the uncertainty in determined structures using the size of the regions in SCS and the variations in atomic coordinates in the structures. The difference in uncertainty between the satisfying structures and the WPS structures illustrates the relative precision that is possible from data alone, versus data and packing together. SYMBRANE simultaneously assigns the intermolecular NOEs during the SCS search for structure determination [118]. This assignment resolves the ambiguity as to which pairs of protons generated the observed NOE peaks, and thus should be restrained in structure determination.

For intersubunit NOEs in symmetric homo-oligomers, the ambiguity includes both the identities of the protons and the identities of the subunits to which they belong. SYMBRANE resolves both ambiguities to determine its structures, and returns all structures consistent with the available data (ambiguous or not). However, while SYMBRANE is complete, it avoids explicit enumeration of the exponential number of combinations of possible assignments. SYMBRANE geometrically prunes SCS regions and NOE assignments that are mutually inconsistent. Pruning occurs only due to provable inconsistency and thereby avoids the pitfall of local minima that could arise from best-first sampling-based approaches. Ultimately, SYMBRANE returns a mutually consistent set of conformations and NOE assignments. SYMBRANE can draw two types of conclusions not possible under previous methods: (a) that different assignments for an NOE would lead to different structural classes, or (b) that it is not necessary to assign an NOE since the choice of assignment would have little impact on structural precision.

In contrast to previous techniques, SYMBRANE separately quantifies the amount of structural constraint provided by data alone, versus data and packing (see figure 18.2d). For the human phospholamban pentamer in dodecylphosphocholine micelles, using the structure of one subunit determined from a subset of the experimental NMR data, SYMBRANE identifies a diverse set of complex structures consistent with the nine intersubunit NOE restraints [117]. The distribution of structures determined in the ensemble (PDB id: 2HYN) provides an objective characterization of structural uncertainty: Incorporating vdW packing reduced the structural diversity by 29% and average variance in backbone atomic coordinates by 44%.

By comparing data consistency and packing quality in a search using different assumptions of oligomeric number, SYMBRANE identified the C5C_5 pentamer as the most likely oligomeric state of phospholamban, demonstrating that it is possible to determine oligomeric number directly from NMR data. Additional tests on six other homo-oligomers, from dimer to heptamer, similarly demonstrated the power of SYMBRANE to provide unbiased determination and evaluation of homo-oligomeric complex structures [117, 118].

Applications and Connections to Other Biophysical Methods

Both NVR and SYMBRANE are structure-based (in that they exploit priors on the monomer structure) and have clear analogies to molecular replacement (MR) in X-ray crystallography and its leverage of subunit structure and non-crystallographic symmetry (NCS). At the heart of NVR is a rotation search (over 3D rotation space, SO(3)SO(3)), and at the core of SYMBRANE is exploitation of the kinematics of CnC_n symmetry. It is possible to generalize and apply these algorithms to help expedite structure determination even using very different experiments (crystallography). To analyze NCS in MR-based X-ray diffraction data of biopolymers, one must “recognize” a finite subgroup of SO(3)SO(3) out of a large set of molecular orientations. This problem may be reduced to clustering in SO(3)SO(3) modulo a finite group, and solved efficiently by “factoring” into a clustering on the unit circle followed by clustering on the 2-sphere S2S^2 , plus some group-theoretic calculations [89]. This yields a polynomial-time algorithm, CRANS, that is efficient in practice, and which enabled determination of the structure of dihydrofolate reductase-thymidylate synthase (DHFR-TS) from Cryptosporidium hominis, PDB id: 1QZF [110, 109, 89]. Cryptosporidium is an organism high on the bioterrorism list of the Centers for Disease Control, a Category B bioterrorist threat. The enzyme DHFR-TS is in the sole de novo biosynthetic pathway for the pyrimidine deoxyribonucleotide dTMP, and therefore an attractive drug target. Solving the structure of DHFR-TS from C. hominis enabled species-specific drug design [5, 116], exploiting structural differences between the human enzyme and C. hominis DHFR-TS.

In general, algorithms like NVR and SYMBRANE are often promiscuous, in that such tools can be applied to many problems in structural biology. The CRANS NCS method for MR [89, 110, 109] in X-ray crystallography generalized NVR rotation search algorithms that were originally proposed for a different problem, NMR assignment [82, 83, 78, 79]. Similarly, work in target selection for structural and functional genomics [84, 81, 87] has applied algorithms from NMR signal processing such as maximum entropy spectral analysis. Recent work on enzyme redesign in the nonribosomal peptide synthetase pathway [88, 136, 45, 44] (using crystallography and site-directed mutations) generalized algorithms for modeling NMR ensembles [49, 11] and rotamers for NOE assignment [153, 174]. These rotamer optimization algorithms [88, 45, 44] can, in turn, be used as a tool in structure determination as discussed below in sections 18.1.3 and 18.1.4.

Looking Under the Hood: How the Algorithms Work, and Outlook for Future Developments

In the future, one expects improvements and extensions to the algorithms described earlier. In particular, the primary goals focus on robustness and scaling. We wish the algorithms to be more robust to noise and missing data. We want the implemented systems to scale, to run successfully on more proteins, and larger proteins. A number of smaller steps and subgoals are foreseen to achieve these goals. In this section, we describe in more detail how the algorithms work so the reader can develop an appreciation both for their scope and how they may be extended and improved.

In general, but particularly for RDC-EXACT, it is useful for the algorithms and software to allow users a choice: to record either (i) one type of backbone RDC (such as NH RDCs) in two aligning media, or (ii) two types of backbone RDCs (such as NH and CH RDCs) in a single medium. This flexibility allows application to a wider range of proteins. Experimental NH RDCs in two media require only an 15N^{15}\text{N} -labeled sample, which is an order of magnitude cheaper to prepare than a doubly labeled 15N/13C^{15}\text{N}/^{13}\text{C} sample. However, finding two aligning media for a protein is not always straightforward; in this case the algorithm can use NH and CH RDCs in a single medium since recording an extra set of RDCs in the same medium requires only slightly more spectrometer time. New methods [127] will be very useful for measuring RDCs in multiple alignment media.

Exact Solutions for Computing Backbone Dihedral Angles from RDCs

RDC-EXACT is an exact-solution, systematic search-based algorithm for structure determination. We now describe the outlook for such algorithms, focusing on robustness and scaling.

RDC-EXACT was developed both as a de novo structure determination algorithm and as a tool in “MR for NMR.” In particular, NVR assignments are structure based. However, RDC-EXACT does not currently exploit (or require) structural priors. Thus, a naïve implementation of the MR-like pathway in figure 15.1 might ignore the structural homolog found by GD, and hence lose information. However, RDC-EXACT could use the structural homologs found by GD as a bias in structure determination. More specifically: RDC-EXACT is currently a de novo structure determination method, starting with resonance assignments. Those assignments could come from either NVR or conventional triple-resonance experiments. Indeed, in the case where GD detects (from unassigned NMR data) a novel fold, not in the database (figure 15.1), one can use algorithms for de novo assignment, that process either triple-resonance experiments or sequential connectivities deduced from short-range NOEs [22, 105, 149, 70, 148, 12]. However, for a non-novel fold, the structural model determined by GD can be exploited to bias the choice in RDC-EXACT of polynomial roots representing the backbone dihedral angles. Initially, these were chosen by Ramachandran fitness; we now describe an improved version of RDC-EXACT that exploits bias toward a priori structure in the regions of regular secondary structure and low dynamics. A series of filters can be employed to choose between the discrete, finite roots representing conformations. These filters (which may be viewed as a fitness function) combine the fit to the data, modeling (Ramachandran fitness), and structural homology (from GD). In the case of missing data [156], or for denatured or disordered proteins [154], one can introduce into the fitness function van der Waals or molecular mechanics energies [114, 15, 117]. This increases reliance on modeling, using an empirical energy function to compensate for missing data. Such fitness functions may combine sources of data and modeling using relative weights. The choice of these weights can be problematic [124]. By converting each term of the fitness function to a Bayesian probability (proposed by Nilges [124], and successfully employed in characterizing denatured structures [154] and automated assignments [105]) the resulting probabilities can be combined as log likelihood (the sum of the logarithms of the probabilities), without explicit weights, thereby reducing subjectivity.

When 13C^{13}\text{C} chemical shifts are available, TALOS [25] can be used for secondary structure determination and to provide restraint on the polynomial roots representing (ϕ,ψ)(\phi, \psi) angles. Once RDC-EXACT has used sparse RDCs to determine the conformations and orientations of elements of secondary structure, these fragments are rigidly translated using sparse NOEs [152, 174] or PREs [154]. Connecting loops between these elements can then be solved (as shown in figure 17.2L and [156, 174]). Without NMR data, this would reduce to the kinematic loop closure problem (KLCP), which can be addressed using computer algebra or optimization techniques [74, 134, 104, 26, 27]. With RDC data, the polynomial system of the KLCP can be combined with the quartic and quadratic RDC polynomials (eqs. 18.6 and 18.9) to simultaneously find satisfying solutions (conformations) to the KLCP and the RDC equations. This simultaneous bicriterion optimization search requires solving higher-degree polynomials, which can be approximated using homotopy continuation or solved exactly using multivariate resultant or Gröbner basis methods, as presented in Donald et al. [37]. Since the Ramachandran plot is less informative for loops, the enhanced filters above, that incorporate packing and empirical molecular mechanics energies, are helpful outside regions of regular secondary structure. One can also employ a modified version of the robotics-based CCD algorithm [174]. One can represent the loop residues as a conformation tree (figure 16.8) [152, 88, 156, 174], and filter/search it for the loop ensemble that best fits the experimental RDCs (and any available long-range NOEs). Recent results suggest that this search can return a structural loop ensemble with good stereochemistry that simultaneously solves the KLCP consistent with the experimental NMR measurements [156, 174].

RDC-EXACT should be particularly useful for the studies of large protein complexes because backbone resonances and associated RDCs can be readily assigned and measured even in a very large protein, such as the 82 kDa malate synthase G [144, 143]. The RDC-EXACT algorithm computes backbone dihedral angles from two RDCs per residue, in constant time per residue. It is possible to derive, from the physics of RDCs, low-degree polynomials (with degree at most 4) whose solutions give the backbone (ϕ,ψ)(\phi, \psi) angles.

We describe the methodology and protocol for exact solutions assuming that we are given assigned NH RDCs in two media. These methods also hold for the case of NH and CH RDCs in one medium with slight modifications to the equations below, as shown in section 16.1 and Wang and Donald [151, 177]. For ease of exposition, we assume that the dipolar interaction constant DmaxD_{max} is equal to 1. By considering a global coordinate frame that diagonalizes the alignment tensor equation (16.1) becomes:

r=Sxxx2+Syyy2+Szzz2,(18.1)r = S_{xx}x^2 + S_{yy}y^2 + S_{zz}z^2, \quad (18.1) where SxxS_{xx} , SyyS_{yy} and SzzS_{zz} are the three diagonal elements of a diagonalized Saupe matrix 𝑺\mathbf{S} (the alignment tensor), and xx , yy and zz are, respectively, the xx , yy , zz -components of the unit vector 𝒗\mathbf{v} in a principal order frame (POF) which diagonalizes 𝑺\mathbf{S} . Now, 𝑺\mathbf{S} is a 3×33 \times 3 symmetric, traceless matrix with five independent elements [140, 1]. Given NH RDCs in two aligning media, the associated NH vector 𝒗\mathbf{v} must lie on the intersection of two conic curves [135, 159]. We now derive the

Wang-Donald equations ( 18.6, 18.9, and 18.12), that permit the (ϕ,ψ)(\phi, \psi) backbone dihedral angles to be solved exactly and in closed form, given protein kinematics and two RDCs per reside. Very similar equations have been derived for NH and CαHαC^\alpha H^\alpha RDCs measured in a single medium (see section 16.1 and [151, 177]).

Proposition 18.1 [152] Given the diagonal Saupe elements SxxS_{xx} and SyyS_{yy} for medium 1, Sxx′S'_{xx} and Syy′S'_{yy} for medium 2 and a relative rotation matrix 𝑹\mathbf{R} between the POFs of medium 1 and 2, the square of the xx -component of the unit vector 𝒗\mathbf{v} satisfies a univariate polynomial quartic equation.

The following is a sketch of the proof. The methods for the computation of the seven parameters (Sxx,Syy,Sxx′,Syy′,and 𝑹12)(S_{xx}, S_{yy}, S'_{xx}, S'_{yy}, \text{and } \mathbf{R}_{12}) and the full expressions for the polynomial coefficients and temporary variables (a2,b2,c1,etc.)(a_2, b_2, c_1, \text{etc.}) can be found in Wang and Donald [152].

Proof sketch Fix a backbone NH vector 𝒗\mathbf{v} along the backbone and let rr (eq. 18.1) and r′=Sxx′x′2+Syy′y′2+Szz′z′2r' = S'_{xx}x'^2 + S'_{yy}y'^2 + S'_{zz}z'^2 be the experimental RDCs for 𝒗\mathbf{v} in the first and second medium, respectively. We have (x′y′z′)T=𝑹(xyz)T(x' \ y' \ z')^T = \mathbf{R}(x \ y \ z)^T , where x,y,zx, y, z are the three components of 𝒗\mathbf{v} in a POF of medium 1, r′r' and x′,y′,z′x', y', z' are the corresponding variables for medium 2. Let 𝑹=(Rij)i,j=1,…,3\mathbf{R} = (R_{ij})_{i,j=1,\dots,3} . Eliminating x′,y′,z′x', y', z' we have

c0=a2x2+b2y2+c1xy+c2xz+c3yz(18.2)c_0 = a_2x^2 + b_2y^2 + c_1xy + c_2xz + c_3yz \quad (18.2)

c4=a1x2+b1y2(18.3)c_4 = a_1x^2 + b_1y^2 \quad (18.3) where a2=(Sxx′−Szz′)(R112−R132)+(Syy′−Szz′)(R212−R232)a_2 = (S'_{xx} - S'_{zz})(R_{11}^2 - R_{13}^2) + (S'_{yy} - S'_{zz})(R_{21}^2 - R_{23}^2) , c2=2(Sxx′−Szz′)R11R13+2(Syy′−Szz′)R21R23c_2 = 2(S'_{xx} - S'_{zz})R_{11}R_{13} + 2(S'_{yy} - S'_{zz})R_{21}R_{23} , and a1,b1,b2,c0,…,c4a_1, b_1, b_2, c_0, \dots, c_4 are similar constants; full details are given in Wang and Donald [152]. Eliminating zz from equation (18.2) we obtain

d8x4+d7x3y+d6x2y2−d5x2+d4xy3−d3xy−d2y2+d1y4+d0=0(18.4)d_8x^4 + d_7x^3y + d_6x^2y^2 - d_5x^2 + d_4xy^3 - d_3xy - d_2y^2 + d_1y^4 + d_0 = 0 \quad (18.4) where d8=a22+c22d_8 = a_2^2 + c_2^2 , and d7,d6,…,d0d_7, d_6, \dots, d_0 are analogously defined; these are fully specified in [152]. (18.4) is a degree 8 polynomial in xx after direct elimination of yy using equation (18.3). However, it can be reduced to a quartic equation by substitution since all terms have even degree. Introducing new variables tt and uu such that

x=asin⁡t,y=bcos⁡t,u=cos⁡2t,(18.5)x = a \sin t, \quad y = b \cos t, \quad u = \cos 2t, \quad (18.5) and through algebraic manipulation we finally obtain the Wang-Donald Equation of type I for NH vectors from RDCs in two media:

f4u4+f3u3+f2u2+f1u+f0=0.(18.6)f_4u^4 + f_3u^3 + f_2u^2 + f_1u + f_0 = 0. \quad (18.6)

The full expressions for coefficients a,b,f0,f1,f2,f3,f4a, b, f_0, f_1, f_2, f_3, f_4 are given in Wang and Donald [152]. Since u=1−2(xa)2u = 1 - 2\left(\frac{x}{a}\right)^2 equation (18.6) is also a quartic equation in x2x^2 . ▫\square

Similar equations to equation (18.6) have been derived for NH and CαHαC^\alpha H^\alpha RDCs measured in a single medium (see section 16.1 and [151, 177]). The yy -component of 𝒗\mathbf{v} can be computed directly from equation (18.5). Due to twofold symmetry in the RDC equation, the number of real solutions for 𝒗\mathbf{v} is at most 8. We will refer to the bond vector between the N and C α^\alpha atoms as the NC α^\alpha vector. Given two unit vectors in consecutive peptide planes we can use backbone kinematics to derive quadratic equations to compute the sines and cosines of the (ϕ,ψ)(\phi, \psi) angles:

Proposition 18.2 [152] Given the NH unit vectors 𝒗i\mathbf{v}_i and 𝒗i+1\mathbf{v}_{i+1} of residues ii and i+1i+1 and the NC α^\alpha vector of residue ii the sines and cosines of the intervening backbone dihedral angles (ϕ,ψ)(\phi, \psi) satisfy the trigonometric equations sin⁡(ϕ+g1)=h1\sin(\phi + g_1) = h_1 and sin⁡(ψ+g2)=h2\sin(\psi + g_2) = h_2 , where g1g_1 and h1h_1 are constants depending on 𝒗i\mathbf{v}_i and 𝒗i+1\mathbf{v}_{i+1} , and g2g_2 and h2h_2 depend on 𝒗i\mathbf{v}_i , 𝒗i+1\mathbf{v}_{i+1} , sin⁡ϕ\sin \phi and cos⁡ϕ\cos \phi . Furthermore, exact solutions for sin⁡ϕ\sin \phi , cos⁡ϕ\cos \phi , sin⁡ψ\sin \psi , and cos⁡ψ\cos \psi can be computed from a quadratic equation by tangent half-angle substitution.

The following is a sketch of the proof. Full expressions for the polynomial coefficients and temporary variables (x1,y1,z1,x2,y2,z2,g1,h1,g2,h2)(x_1, y_1, z_1, x_2, y_2, z_2, g_1, h_1, g_2, h_2) introduced in the proof are given in Wang and Donald [152].

Proof sketch Using backbone inverse kinematics, the two NH vectors 𝒗i\mathbf{v}_i and 𝒗i+1\mathbf{v}_{i+1} can be related by 8 rotation matrices between two coordinate systems in peptide planes ii and i+1i+1 :

𝒗i=𝑹x(θ7)𝑹y(θ6)𝑹x(θ5)𝑹z(ψ+π)𝑹x(θ3)𝑹y(ϕ)𝑹y(θ8)𝑹x(θ1)𝒗i+1.(18.7)\mathbf{v}_i = \mathbf{R}_x(\theta_7)\mathbf{R}_y(\theta_6)\mathbf{R}_x(\theta_5)\mathbf{R}_z(\psi + \pi)\mathbf{R}_x(\theta_3)\mathbf{R}_y(\phi)\mathbf{R}_y(\theta_8)\mathbf{R}_x(\theta_1)\mathbf{v}_{i+1}. \quad (18.7)

The definitions of the coordinate systems, the expressions for the rotation matrices 𝑹x\mathbf{R}_x , 𝑹y\mathbf{R}_y and 𝑹z\mathbf{R}_z and the definitions of the six backbone angles (θ1,θ3,θ5,θ6,θ7(\theta_1, \theta_3, \theta_5, \theta_6, \theta_7 , and θ8\theta_8) are given in Wang and Donald [152]. The backbone (ϕ,ψ)(\phi, \psi) angles are defined according to the standard convention. Given the values of these six angles 𝑹i=𝑹x(θ7)𝑹y(θ6)𝑹x(θ5)\mathbf{R}_i = \mathbf{R}_x(\theta_7)\mathbf{R}_y(\theta_6)\mathbf{R}_x(\theta_5) and 𝑹r=𝑹y(θ8)𝑹x(θ1)\mathbf{R}_r = \mathbf{R}_y(\theta_8)\mathbf{R}_x(\theta_1) are two 3×33 \times 3 constant matrices. Define two new vectors 𝒘1=(x1,y1,z1)=𝑹i−1𝒗i\mathbf{w}_1 = (x_1, y_1, z_1) = \mathbf{R}_i^{-1}\mathbf{v}_i and 𝒘2=(x2,y2,z2)=𝑹r𝒗i+1\mathbf{w}_2 = (x_2, y_2, z_2) = \mathbf{R}_r\mathbf{v}_{i+1} to obtain

x1=−(cos⁡ϕcos⁡ψ+sin⁡θ3sin⁡ϕsin⁡ψ)x2−cos⁡θ3sin⁡ψy2+(cos⁡ψsin⁡ϕ−cos⁡ϕsin⁡θ3sin⁡ψ)z2y1=(cos⁡ϕsin⁡ψ−sin⁡θ3sin⁡ϕcos⁡ψ)x2−cos⁡θ3cos⁡ψy2−(sin⁡ϕsin⁡ψ+cos⁡ϕsin⁡θ3cos⁡ψ)z2z1=cos⁡θ3sin⁡ϕx2−sin⁡θ3y2+cos⁡θ3cos⁡ϕz2.(18.8)\begin{aligned} x_1 &= -(\cos \phi \cos \psi + \sin \theta_3 \sin \phi \sin \psi)x_2 - \cos \theta_3 \sin \psi y_2 + (\cos \psi \sin \phi - \cos \phi \sin \theta_3 \sin \psi)z_2 \\ y_1 &= (\cos \phi \sin \psi - \sin \theta_3 \sin \phi \cos \psi)x_2 - \cos \theta_3 \cos \psi y_2 - (\sin \phi \sin \psi + \cos \phi \sin \theta_3 \cos \psi)z_2 \\ z_1 &= \cos \theta_3 \sin \phi x_2 - \sin \theta_3 y_2 + \cos \theta_3 \cos \phi z_2. \end{aligned} \quad (18.8)

By equation (18.8) we can then obtain the Wang-Donald Equation of type II for the ϕ\phi dihedral angle from RDCs in two media:

sin⁡(ϕ+g1)=h1,(18.9)\sin(\phi + g_1) = h_1, \quad (18.9) where

h1=z1+y2sin⁡θ3(x2cos⁡θ3)2+(z2cos⁡θ3)2,(18.10)h_1 = \frac{z_1 + y_2 \sin \theta_3}{\sqrt{(x_2 \cos \theta_3)^2 + (z_2 \cos \theta_3)^2}}, \quad (18.10) and g1g_1 is a similar constant; see Wang and Donald [152] for details. The values of sin⁡ϕ\sin \phi and cos⁡ϕ\cos \phi can be computed from a quadratic equation by the substitution

w=tan⁡ϕ2,sin⁡ϕ=2w1+w2,cos⁡ϕ=1−w21+w2(18.11)w = \tan \frac{\phi}{2}, \sin \phi = \frac{2w}{1+w^2}, \cos \phi = \frac{1-w^2}{1+w^2} \quad (18.11)

Substituting the computed sin⁡ϕ\sin \phi and cos⁡ϕ\cos \phi into equation (18.8), we can obtain the analogous equation of type II for the ψ\psi dihedral angle from RDCs in two media [152]; it is another simple trigonometric equation:

sin⁡(ψ+g2)=h2.(18.12)\sin(\psi + g_2) = h_2. \quad (18.12)

Hence, sin⁡ψ\sin \psi and cos⁡ψ\cos \psi can be computed similarly from a quadratic equation where both g2g_2 and h2≤1h_2 \leq 1 are computed from y1,x2,y2,z2,θ3,sin⁡ϕy_1, x_2, y_2, z_2, \theta_3, \sin \phi , and cos⁡ϕ\cos \phi . ▫\square

Similar equations to equations (18.9–18.12) have been derived for NH and CαHαC^\alpha H^\alpha RDCs measured in a single medium (see section 16.1 and [151, 177]).

The structures computed by RDC-EXACT may be slightly different from structures computed using traditional protocols (section 17.1), which use different data, more data, and rely more on modeling. In contrast to, for example, simulated annealing approaches, RDC-EXACT is built on the exact solutions for computing backbone (ϕ,ψ\phi, \psi) angles from RDC data and systematic search. RDC-EXACT is guaranteed to compute the global minimum (the best fit, or maximum likelihood solution to the data) and hence is provable in terms of completeness, correctness, and complexity. We caution that in the context of RDC-EXACT, the term “provably correct” refers to the computational correctness of the algorithm. It is not meant to imply that the RDC-EXACT structures computed using the preceding modeling assumptions (i.e., standard protein covalent geometries, pruning of (ϕ,ψ\phi, \psi) solutions using the Ramachandran plot and steric clashes) will always compute biologically correct structures. More precisely, the proofs guarantee accuracy (of the computed structures) and optimality (of the maximum likelihood structure) up to, but only up to, the accuracy of the modeling assumptions. One can relax the modeling assumptions and improve their accuracy, as outlined earlier. However, a helpful first step has been to develop an algorithm that is provably correct up to the limitations of the initial model. It is unusual for protein structure determination algorithms to have guarantees of computing the optimal structure, in polynomial time. RDC-EXACT has both these desirable properties [156, 177], and hence promises significant advantages as a method to compute structures accurately using only very sparse restraints.

For smaller proteins it may be possible to collect side-chain RDCs, in which case RDC-EXACT can be extended to compute side-chain conformations. One can extend the algorithms to compute complete protein structures (including side-chains), since exact equations analogous to equations (18.6 and 18.9) can be derived mutatis mutandis to compute the side-chain dihedral angles χ1,χ2,…\chi_1, \chi_2, \dots from side-chain RDCs. In this case, the average or Ramachandran angles used as root-filters in Wang and Donald [152], may be replaced with modal side-chain rotamer library angles χa,1,χa,2,…\chi_{a,1}, \chi_{a,2}, \dots . One can also expedite protein structure determination using pseudocontact shift restraints [72] or carbonyl chemical shift anisotropy upon alignment [167], since similar equations can be derived for computing the corresponding vector orientations and dihedral angles.

Nuclear Vector Replacement and Fold Recognition Using Unassigned RDCs

NVR-like algorithms for automated assignment form a cornerstone for molecular-replacement (MR) type methods for NMR starting with only unassigned data. Since GD can be viewed as the application (filtering) of NVR modules to a database (as opposed to a single structure), improvements to NVR will, mutatis mutandis, improve the accuracy and performance of GD. Note that unlike MR (in crystallography), NVR/GD is sufficiently efficient computationally that it can be applied to thousands of template structures in a short time.

NVR uses two classes of constraints: geometric and probabilistic (see figure 17.3). The HN-15N\text{H}^N\text{-}^{15}\text{N} RDC, H-D exchange and 15N-NOESY^{15}\text{N}\text{-NOESY} each provide independent geometric constraints on assignment. A sparse number of dNNSd_{\text{NNS}} are extracted from the unassigned NOESY after the diagonal peaks of the NOESY are cross-referenced to the peaks in the HSQC. These dNNSd_{\text{NNS}} provide distance restraints for assignments. In general, there are only a small number of unambiguous dNNSd_{\text{NNS}} that can be obtained from an unassigned 3D 15N^{15}\text{N} -edited NOESY. The amide exchange information probabilistically identifies the peaks in the HSQC corresponding to non-hydrogen-bonded, solvent-accessible backbone amide protons. RDCs provide probabilistic constraints on each backbone amide-bond vector’s orientation in the POF. Finally, chemical shift prediction is employed [79] to compute a probabilistic constraint on assignment. NVR exploits the geometric and probabilistic constraints by combining them within an Expectation/Maximization framework.

NVR can be improved by exploiting different, but still efficient experiments. Currently, NVR uses amide exchange experiments to distinguish surface from buried residues [79]. This “inside/outside” information is correlated with the structural model, and increases assignment accuracy. When these experiments may be impractical for larger proteins, one can, in principle, employ paramagnetic quenching [172] or “water HSQC” experiments [41, 51], which identify fast-exchanging or solvent-exposed backbone protons. Since this information is complementary to the slow-exchange protons identified by H-D exchange, it likely could be integrated into NVR by complementing the corresponding edge weights in a bipartite graph, which we shall discuss later. Similarly, it is probable that assignment accuracy will be improved by incorporating CH RDCs into NVR and GD, since in helices the Cα-Hα\text{C}^\alpha\text{-H}^\alpha bond vector orientations are less degenerate than NH vectors, thereby both improving tensor accuracy in the bootstrapping phase and increasing disambiguation of helical RDCs in the assignment phase. Four-dimensional 15N-,15N-^{15}\text{N}\text{-},^{15}\text{N}\text{-} and 13C-,15N-edited NOESY^{13}\text{C}\text{-},^{15}\text{N}\text{-edited NOESY} experiments [21] from singly and doubly labeled samples, respectively, will reduce the ambiguity in both spin systems and assignments, and facilitate matching of NOE restraints to structural models. While the acquisition time for 4D NOESY is longer, the direct polar Fourier transformation holds great potential to speed up data collection significantly, by producing quantitatively accurate spectra from radial and concentric sampling [23, 13].

The ultimate goal is to make NVR useful in an analogous manner to molecular replacement (MR) in crystallography. To do this NVR has been extended to operate on more distant structural homologs [8]. The relative sensitivity of RDCs to structural noise is evident in equation (16.1), from the quadratic dependence on the bond vector 𝒗\mathbf{v} versus the linear dependence on the alignment tensor 𝑺\mathbf{S} . In the NVR scoring function, the MM step of the EM algorithm uses edge weights to compute the joint probability of the resonance assignments in an ensemble of bipartite graphs. This score is a maximum likelihood estimator of assignment accuracy, and as parameters and inputs to the algorithm (such as the structural model and alignment tensor) are varied, its log likelihood may be optimized. As cross-validation, an alternative scoring function, proposed in Langmead and Donald [79], employs the mean tensor consistency computed from an ensemble of subsets of assignments against the structural model. In principle, both methods allow a parametric family of structural models to be explored about the putative homolog, enabling NVR to bootstrap assignments analogously to the role of MR, starting with a structural homolog in crystallography. Indeed, traditional (X-ray) MR had previously been extended to solve phase problems from more distant models by using normal mode analysis (NMA) [138, 137]. Analogously, one can perform a geometric exploration of conformation space to generate an ensemble of neighboring structures to the initial homolog using NMA [8].

NMA can be performed as described traditionally [58, 17] or with a Gaussian network model [141]. It would also be valuable to compare and geometrically simulate diffusive motions to sample the internal mobility of the protein using alternative techniques such as FRODA, FIRST, and ROCK [65, 173, 161], that are based on graph rigidity theory. The structures that maximize the likelihood of assignment accuracy can then be used for NVR [8]. An allied idea was used earlier by Baker and coworkers for decoy detection in the context of pruning structure predictions by NMR data [97]. NVR-NMA ensembles [8] are different in that they systematically represent the deformation space for equilibrium protein motions, rather than a family that mixes correct and incorrect structures. It appears that as in Suhre and Sanejouand [138], the NMA-like approaches above can adequately sample the necessary convolution of structural variation, noise, and dynamics around the target structure [8].

We now describe a number of key technical and algorithmic features of NVR. NVR uses a variation of the EM algorithm [79], which is a statistical method for computing the maximum likelihood estimates of parameters for a generative model. EM has been a popular technique in a number of different fields, including machine learning and image understanding. It has been applied to bipartite matching problems in computer vision [30]. Bipartite matching is extremely sensitive to noise in the edge weights. There is evidence that sophisticated algorithms such as EM or NVR must be employed if bipartite matching is to be used as a subroutine on data that is sparse or noisy [79, 8]. In the EM framework there are both observed and hidden (i.e., unobserved) random variables. In the context of structure-based assignment, the observed variables are the chemical shifts, unassigned dNNSd_{\text{NNS}} , amide exchange rates, RDCs, and the 3D structure of the target protein.

Let XX be the set of observed variables. The hidden variables Y=YG∪YSY = Y_G \cup Y_S are the true (i.e., correct) resonance assignments YGY_G , and YSY_S , the correct, or “true” alignment tensors. Of course, the values of the hidden variables are unknown. Specifically, YGY_G is the set of edge weights of a bipartite graph, G={K,R,K×R}G = \{K, R, K \times R\} , where KK is the set of peaks in the HSQC and RR is the set of residues in the protein. The weights YGY_G represent correct assignments, and therefore encode a perfect matching in GG . Hence, for each peak k∈Kk \in K (respectively, residue r∈Rr \in R), exactly one edge weight from kk (respectively rr) is 1 and the rest are 0.

The probabilities on all variables in YY are parameterized by the “model,” which is the set Θ\Theta of all assignments made so far by the algorithm. Initially, Θ\Theta is empty. As EM makes more assignments, Θ\Theta grows, and both the probabilities on the edge weights YGY_G and the probabilities on the alignment tensor values YSY_S will change. The goal of the EM algorithm is to estimate YY accurately to discover the correct edge weights YGY_G , thereby computing the correct assignments. The EM algorithm has two steps; the Expectation (EE) step and the Maximization (MM) step. The EE step computes the expectation E(Θ∪Θ′|Θ)=E(log⁡𝑷(X,Y|Θ∪Θ′))E(\Theta \cup \Theta' | \Theta) = E(\log \mathbf{P}(X, Y | \Theta \cup \Theta')) . Here, Θ′\Theta' is a nonempty set of candidate new assignments that is disjoint from Θ\Theta . The MM step computes the maximum likelihood new assignments Θ*=arg⁡max⁡E(Θ∪Θ′|Θ)\Theta^* = \arg \max E(\Theta \cup \Theta' | \Theta) . Then the master list of assignments is updated, Θ←Θ∪Θ*\Theta \leftarrow \Theta \cup \Theta^* .

The alignment tensors are recomputed at the end of each iteration, using all the assignments in Θ\Theta . Thus, the tensor estimates will be continually refined during the run of the algorithm. The algorithm terminates when each peak has been assigned.

Care must be taken to implement the probabilistic EM framework efficiently (for details see [79]). In brief, individual bipartite graphs are constructed for each of the 7 sources of data (see figure 17.3). NVR operates on bipartite graphs between peaks and residues. The edge weights from each peak to all residues form a probability distribution. The probabilities are derived from (1) “inside/outside” experiments (H-D exchange, paramagnetic quenching), (2) dNNSd_{\text{NNS}} , (3) chemical shift predictions based on average chemical shifts from the BMRB [132], (4) chemical shift predictions made by the program SHIFTS [169], (5) chemical shift predictions made by the program SHIFTX [101], and (6–7) constraints from RDCs in two media.

Data (1–7) above are converted into constraints on assignment. The difference between the experimentally determined chemical shifts and the set of predicted chemical shifts are converted into assignment probabilities. Let 𝑺1\mathbf{S}_1 and 𝑺2\mathbf{S}_2 be the alignment tensors computed from unassigned data as described in section 17.2 and other studies [79, 82, 83, 78]. The amide bond vectors from the structural model are used to back-compute a set of RDCs using equation (16.1). The difference between each back-computed RDC and each experimentally recorded RDC is converted into a probability on assignment. Let DmD_m be the set of observed RDCs in medium mm , and FmF_m be the set of back-computed RDCs using the model and 𝑺m\mathbf{S}_m . Two bipartite graphs M1M_1 and M2M_2 are constructed on the peaks in KK and residues in RR . The edge weights are computed as probabilities as follows: w(k,r)=𝑷(k↦r|Sm)=g(k,r)w(k, r) = \mathbf{P}(k \mapsto r | S_m) = g(k, r) where k∈Kk \in K and r∈Rr \in R . Here, g(k,r)=𝒩(dm(k)−bm(r),σm)g(k, r) = \mathcal{N}(d_m(k) - b_m(r), \sigma_m) where dm(k)∈Dmd_m(k) \in D_m , bm(r)∈Fmb_m(r) \in F_m . The probabilities are computed using a 1-dimensional Gaussian distribution 𝒩(x−μ,σ)=1σ2πexp⁡(−(x−μ)22σ2)\mathcal{N}(x - \mu, \sigma) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right) , with mean dm(k)−bm(r)d_m(k) - b_m(r) and standard deviation σm\sigma_m . Langmead et al. [79] used σ=L/8\sigma = L/8 Hz in their experiments (section 17.2), where LL is the range of the RDCs in that medium (the maximum-valued RDC minus the minimum valued RDC). If an RDC is missing in medium ii for a peak kk , then we set the weight w(k,r)=1/n0w(k, r) = 1/n_0 in graph MiM_i , for each residue rr of the n0n_0 remaining (i.e., unassigned) residues. The details of how the chemical shifts, dNNSd_{\text{NNS}} , and amide exchange rates are converted into constraints on assignment are analogous (see [79]).

NVR uses a unique voting scheme for combining multiple sources of information [8, 79]. For each possible combination of data (1–7) above, a combined graph is constructed whose edge weights are the joint probabilities of the edges in the single-spectra graphs. NVR then constructs a new bipartite graph VV , called the expectation graph, whose edge weights are initialized to 0. For each combined graph cc , we compute a maximum bipartite matching. Let Hc⊂EH_c \subset E be the matching computed on cc . For each edge e∈Hce \in H_c NVR increments the weight on the same edge in the expectation graph, VV , by 1. This is done for all combined graphs. Hence, each bipartite matching “votes” for a set of edges. Thus, edge weights in VV record the number of times a particular edge was part of a maximum bipartite matching. Note that the edge weights are probabilities in the bipartite graphs. Thus, a bipartite matching gives a maximum likelihood solution on that graph, which in turn maximizes the expected log-likelihood of the average edge weight.

Let w0w_0 be the largest edge weight in VV . The MM step is computed, and assignments are made by Θ←Θ∪w−1(w0)\Theta \leftarrow \Theta \cup w^{-1}(w_0) . As previously stated, each of the constituent votes used to construct VV is a maximum likelihood solution. Hence, it maximizes the expected edge weight in the matching. Therefore, in the bipartite graph VV , those edges with maximum votes have the highest expected values over all combinations of the data, thus correctly computing the maximum likelihood new assignments Θ*\Theta^* as the argmax in the MM -Step described earlier.

When an assignment is made, the associated nodes k∈Kk \in K and r∈Rr \in R are removed from BNOEB_{\text{NOE}} , the NOE graph. The geometric NOE restraints are applied to prune matching. The three graphs for chemical shift prediction are synchronized with BNOEB_{\text{NOE}} so that all graphs have the same set of zero-weight edges. Each graph is then renormalized so that the edge weights from each peak form a probability distribution. This completes a single iteration of the EM algorithm.

Recently, a new version of the GD module of NVR, called HD, improved the accuracy of NVR/GD [80]. In particular, HD eliminates the false-positives evident in figure 17.5, even against a larger database of 4,500 folds (versus only 2,456 in GD [78]; see figure 18.1 and [80]). Furthermore, it has been found that combining HD with NMA ensembles (described above) can boost the assignment accuracy using distant structural homologs (3-7 Å backbone RMSD) by up to 22% [8].

The advantage of NVR over maximum bipartite matching lies in its iterative nature. NVR takes a conservative approach, making only likely assignments, given the current information. After making these assignments, the edge weights between the remaining unassigned peaks and residues are updated. Suppose that, during the ithi^{\text{th}} iteration of the algorithm, peak kk is assigned to residue rr . The edge weight between peak kk and residue rr is then set to 1, indicating the certainty of that assignment. The edge weights form a probability distribution. Accordingly, the edge weight between peak kk and any other residue is set to 0. Similarly, the weights on the edges from any other peak to rr are immediately set to 0. The (nonzero) edge weights from each remaining unassigned peak are renormalized prior to the next iteration. Thus, a peak whose assignment may be ambiguous in iteration ii may become unambiguous in iteration i+1i + 1 .

Figure 18.1 Improved fold detection from unassigned NMR data [80]: (a) score computed by HD versus backbone RMSD (Å). The line is a least-squares fit to the data. The correlation coefficient is -0.75. Open diamonds are homologous structures with low sequence similarity, detected by HD score ≥−10\geq -10 (table b). Solid diamonds are structures classified as nonhomologs by HD score <−10< -10 (table c). Tables b-c: (a) 3 test proteins: (i) ubiquitin, (ii) G α\alpha IP, (iii) SPG. bPDB/chain Id for the structures detected by HD. cSequence identity of the 3 test proteins(a) vs. the primary sequence of the structure. bd Backbone RMSD between the structuresb and the native structures of the test proteins. (a) cScore computed by the algorithm HD. Higher HD scores (closer to 0) indicate closer structural similarity. Table (B) does not include those structures detected by HD that have >30%> 30\% sequence identity. Copyright 2004 IEEE.

Somewhat surprisingly, results of perturbation studies [79, pp. 120–130] suggest that NVR is not very sensitive to the quality of the initial tensor estimates, because the additional, non-RDC lines of evidence (chemical shift prediction, amide exchange, dNNd_{\text{NN}} ’s) can overcome these inaccuracies. The NVR voting algorithm (see above and [79, 8]) used to integrate different lines of evidence is essentially a means to increase the signal-to-noise ratio. Here, the signal is the computed likelihood of the assignment between a peak and the (correct) residue. The noise is the uncertainty in the data, where the probability mass is distributed among multiple residues. Each line of evidence (i.e., experiment) has noise, but the noise tends to be random and thus cancels when the lines of evidence are combined. Conversely, the signals embedded in each line of evidence tend to reinforce each other, resulting in (relatively) unambiguous assignments. Hence, even if the two initial tensor estimates are poor, it is unlikely that they can conspire (by voting together) to force an incorrect assignment. More generally, given the NVR voting scheme (above, and [79, 8]), any pair of lines of evidence is unlikely to outvote the majority. Finally, the iterative update (described above) by the alignment tensors at each cycle of the EM, allows the tensor accuracy to improve as more assignments are made [79].

Automated NOE Assignment

TRIANGLE is discussed for illustrative purposes; the interested reader is referred to HANA [174] for a more sophisticated algorithm with the same flavor. The TRIANGLE [153] and HANA [174] algorithms for automated NOE assignment use a rotamer library ensemble and RDCs. Both algorithms employ a rotamer-library-derived ensemble of intra-and interresidue vectors between the backbone atoms and side-chain protons to reduce the ambiguity in the assignment of NOE restraints involving side-chain protons, especially aliphatic protons. For example, consider the putative assignment of an NOE to an (HN,Hδ)(H^N, H^\delta) (respectively, (Hα,Hδ)(H^\alpha, H^\delta)) pair of protons. The triangle relationship (see figure 17.5L) defines a decision procedure to filter NOE assignments by fusing information from RDCs (𝒗Nβ\mathbf{v}_{N\beta}), rotamer modeling (𝒗βδ\mathbf{v}_{\beta\delta}), and NOEs (|𝒗Nδ||\mathbf{v}_{N\delta}|). Specifically,

Proposition 18.3 [153] Given the vector 𝒗βδ\mathbf{v}_{\beta\delta} from a CβC^\beta atom to a side-chain proton SS (e.g., HδH^\delta), and the vector 𝒗Nβ\mathbf{v}_{N\beta} from the backbone HNH^N to the CβC^\beta (respectively, the vector 𝒗αβ\mathbf{v}_{\alpha\beta} from the HαH^\alpha atom to CβC^\beta), the vector 𝒗NS\mathbf{v}_{NS} from the HNH^N to SS (respectively, the vector 𝒗αS\mathbf{v}_{\alpha S} from the HαH^\alpha to SS) can be computed by: 𝒗NS=𝒗Nβ+𝒗βδ\mathbf{v}_{NS} = \mathbf{v}_{N\beta} + \mathbf{v}_{\beta\delta} , 𝒗αS=𝒗αβ+𝒗βδ\mathbf{v}_{\alpha S} = \mathbf{v}_{\alpha\beta} + \mathbf{v}_{\beta\delta} .

𝒗Nβ\mathbf{v}_{N\beta} , and 𝒗αβ\mathbf{v}_{\alpha\beta} are computed directly from the backbone structure determined by RDC-EXACT and can be inter-or intraresidue. The vectors 𝒗NS\mathbf{v}_{NS} , 𝒗Nβ\mathbf{v}_{N\beta} , and 𝒗βδ\mathbf{v}_{\beta\delta} form three sides of a triangle (figure 17.5), where 𝒗Nβ\mathbf{v}_{N\beta} is computed from the backbone structure and 𝒗βδ\mathbf{v}_{\beta\delta} lies in a finite set of vectors, mined from the PDB rotamers. Hence, for each side-chain proton, 𝒗βδ\mathbf{v}_{\beta\delta} lies in a finite set of vectors. Consequently, there is a finite set VNV_N (respectively VαV_\alpha) of vectors containing 𝒗NS\mathbf{v}_{NS} (respectively 𝒗αS\mathbf{v}_{\alpha S}). The triangle relationship (Proposition 18.1.3) is then used to filter the assignments of NOE peaks involving side-chain protons. The algorithm first estimates the NOE distances, dNd_N and dαd_\alpha , using the NOE intensities from, respectively, the experimental NOE peaks picked from the 3D 15N^{15}\text{N} - and 13C^{13}\text{C} -NOESY spectra. TRIANGLE tests dNd_N and dαd_\alpha to see whether they satisfy the constraints: min⁡|𝒗NS|−εN≤dN≤max⁡|𝒗NS|+εN\min |\mathbf{v}_{NS}| - \varepsilon_N \leq d_N \leq \max |\mathbf{v}_{NS}| + \varepsilon_N , min⁡|𝒗αS|−εα≤dα≤min⁡|𝒗αS|+εα\min |\mathbf{v}_{\alpha S}| - \varepsilon_\alpha \leq d_\alpha \leq \min |\mathbf{v}_{\alpha S}| + \varepsilon_\alpha , where min\min and max\max for 𝒗NS\mathbf{v}_{NS} (respectively, 𝒗αS\mathbf{v}_{\alpha S}) are both computed over 𝒗NS∈VN\mathbf{v}_{NS} \in V_N (respectively, 𝒗αS∈Vα\mathbf{v}_{\alpha S} \in V_\alpha). εN\varepsilon_N and εα\varepsilon_\alpha are the NOE distance error bounds for the corresponding 3D 15N^{15}\text{N} - (respectively, 13C^{13}\text{C} -) edited NOESY peaks.

Tests of TRIANGLE and HANA are described in section 17.4 and other studies [153, 174, 177]. In the future, it will be important to quantify any possible bias introduced by the rotamer library, using both rotamer subsampling and rotamer energy minimization (generalizing prior work on rotamer optimization [88, 45, 44]), and comparison to conventional assignments. For example, one can use a subsampled rotamer library that is more than 6,000 times finer than the library in Wang and Donald [153]. In preliminary tests on ubiquitin NOE spectra, the finer library resulted in modest improvements in assignment accuracy (about 5%) at a considerable computational cost (2 hours versus 1 second). This suggests that the optimal number of rotamers should lie in between.

Further study is required of the effect of spin diffusion on cross-peak intensity and the NOE distance |𝒗Nδ||\mathbf{v}_{N\delta}| in the triangle relationship (figure 17.5L) for assignment pruning. An extension of TRIANGLE has been used with RDC-EXACT to assign the NOEs and compute structures, including side-chains [174]. It will be valuable to extend TRIANGLE to account for the various labeling patterns necessary in large proteins to solve the structures of such large systems. These labeling strategies can sometimes vitiate the HCCH-TOCSY [108] for side-chain resonance assignments. One can extend TRIANGLE to assign NOEs involving these ambiguous proton resonances, by replacing their side-chain assignment with a set of possible labels (analogous to [1]). The labels, which represent competing assignments for the indirect 1H^1\text{H} dimension, can be pruned using Proposition 18.1.3. The resulting NOESY assignments from TRIANGLE would provide side-chain resonance assignments as a byproduct. This extension to TRIANGLE would not only reduce the dependence of NOE assignment algorithms upon the (less sensitive) TOCSY experiments, but also increase their tolerance of incomplete side-chain resonance assignments.

Side-chain/side-chain NOEs may be assigned by “lifting” TRIANGLE’s rotamer-based ensemble of internuclear vectors (via Cartesian product). 4D NOESY experiments can expedite TRIANGLE’s computation of these assignments. A discussion of the information content of 4D NOESY versus selective labeling is therefore warranted. TRIANGLE and its successor, HANA [174], employ a “symmetry check” [60] to increase assignment confidence using “back” NOEs. Consider a putative assignment for an NOE, 15N−HN↔1H^{15}\text{N}-\text{H}^N \leftrightarrow ^1\text{H} , where ω(1H)\omega(^1\text{H}) is assigned to 1Hδ^1\text{H}^\delta of F16. If the assignment is correct, then we should see a symmetric NOE in the 13C^{13}\text{C} -NOESY: HN↔1Hδ−13Cδ\text{H}^N \leftrightarrow ^1\text{H}^\delta-^{13}\text{C}^\delta of F16. Finding this peak requires searching a box in the 3D 13C^{13}\text{C} -NOESY, about the (HN,1H,13Cδ)(\text{H}^N, ^1\text{H}, ^{13}\text{C}^\delta) shifts. Since the “back” NOE might be missing and there might be other peaks in this box, the symmetry check must be treated inferentially, as changing the Bayesian probability of the assignment. Using a 4D NOESY reduces this ambiguity, and in principle the symmetric interaction will always be observed. As a pruning condition, back NOEs and 4D NOEs complement the Triangle Relationship (Proposition 18.1.3) by integrating the geometric and spectral constraint of the additional observed 13Cδ^{13}\text{C}^\delta . However, under some isotopic labeling schemes, 4D NOEs to protons bonded to 12C^{12}\text{C} will not be observed, and the previously described set-of-labels strategy must be employed. Finally, TRIANGLE and HANA should be helpful to assist with proposed experimental methods for 24–65 kDa proteins that currently use manual 4D NOE assignment (e.g., [170]), which could then be automated, saving time and reducing subjectivity.

NMR Structure Determination of Symmetric Oligomers

Many experimental challenges exist for determining the structure of membrane protein complexes. Current algorithms in this area, including SYMBRANE (section 17.5) do not address all of these problems, and make a number of assumptions. Most important, it can sometimes be assumed that the overall fold of a subunit can be obtained from RDCs and other NMR measurements in the holo state, and that intersubunit NOEs can be distinguished from intrasubunit NOEs using isotope filtering, as was done for phospholamban [111, 117]. In particular, the automated ambiguous intersubunit NOE assignment in SYMBRANE relies on these assumptions [118].

One wishes to extend and relax these assumptions; although a long-term goal is to develop algorithms for general membrane proteins, this chapter focuses next on the challenges of symmetric oligomers, which include many biomedically important systems. Moreover, RDCs can play a crucial role for such complexes, not only in determining the conformation and orientation of the individual subunits, but also in computing the symmetry axis. The overall scheme of SYMBRANE is shown in figure 18.2 (plate 22). In contrast, traditional protocols [102] for structure determination of protein complexes from NMR data use simulated annealing (SA) and molecular dynamics (MD). However, the SA/MD mechanism is not complete and could get trapped in local minima. Furthermore, the precision of the determined structure is strongly affected by the temperature. SYMBRANE avoids temperature dependence and local minima problems, and does not suffer from “false precision” in characterizing the diversity of determined structures. SYMBRANE’s search in the symmetry configuration space (SCS) takes advantage of the “closed-ring” constraint of a symmetric homo-oligomer. AMBIPACK [150] used a branch-and-bound algorithm to compute rigid body transformations satisfying potentially ambiguous intersubunit distance restraints. In contrast, SYMBRANE uses the oligomeric number to enforce an a priori symmetry constraint. In this sense it is analogous to the manner in which noncrystallographic symmetry is handled in molecular replacement for X-ray crystallography [89]. By formulating the structure determination problem in the SCS rather than in the space of atom positions, SYMBRANE is able to exploit directly the kinematics of the “closed-ring” constraint, and thereby derive an analytical bound for pruning, which is tighter and more accurate than previous randomized numerical techniques [150]. SYMBRANE’s guarantees of completeness should be especially important for membrane proteins (where sparse data is a particularly important problem), but should also prove useful for water-soluble oligomers.

SYMBRANE simultaneously assigns NOEs and determines structure (by identifying regions in SCS), and is guaranteed to find all consistent assignments and structures [118]. Let RR be a set of (possibly ambiguous) NOEs. Let rklr_{kl} represent the lthl^{\text{th}} possible assignment of the kthk^{\text{th}} NOE rkr_k of RR , and let skl⊂S2×ℝ2s_{kl} \subset S^2 \times \mathbb{R}^2 (see figure 18.2a) be the region of the SCS in which distance restraint rklr_{kl} is satisfied. An assignment specifies the subunit and the protons involved in the NOE. A determined structure must satisfy all ambiguous NOEs; it satisfies each by satisfying one or more of its possible assignments. In the SCS, this translates into finding the region

p(R)=(s11∪s12∪s13∪…)∩(s21∪s22∪…)∩…=⋂k=1∥R∥(⋃l=1tkskl),(18.13)p(R) = (s_{11} \cup s_{12} \cup s_{13} \cup \dots) \cap (s_{21} \cup s_{22} \cup \dots) \cap \dots = \bigcap_{k=1}^{\|R\|} \left( \bigcup_{l=1}^{t_k} s_{kl} \right), \quad (18.13)

Figure 18.2 (plate 22) SYMBRANE Algorithm. (a) Given the subunit structure, the relative position 𝒕∈ℝ2\mathbf{t} \in \mathbb{R}^2 and orientation 𝒂∈S2\mathbf{a} \in S^2 of the symmetry axis uniquely determines structure. Structure determination is a search problem in 4-dimensional symmetry configuration space (SCS), S2×ℝ2S^2 \times \mathbb{R}^2 . An NOE is shown between protons 𝒑\mathbf{p} and 𝒒′\mathbf{q}' [117]. (b) The branch-and-bound algorithm proceeds as a tree search in SCS. The 4D SCS is represented as two 2D regions, a sphere representing the orientation space S2S^2 and a square representing the translation space ℝ2\mathbb{R}^2 . The dark shaded regions at each node of the tree represent the region in SCS being explored ( A×T⊂S2×ℝ2A \times T \subset S^2 \times \mathbb{R}^2 ). Ultimately (bottom left of the tree), the branch-and-bound search returns regions in 4D space representative of structures that possibly satisfy all the restraints. At each node, we test satisfaction of each restraint of form 𝒑𝒒′≤d\mathbf{p}\mathbf{q}' \leq d by testing intersection between the ball of radius dd centered at 𝒑\mathbf{p} and the convex hull bounding possible positions of 𝒒′\mathbf{q}' . If there exists an intersection between the ball and the convex hull for each restraint, further branching is done (node 1); otherwise, the entire node and its subtree are pruned (node 2) [117]. (c) Representative results: complete ensemble of NMR structures of the unphosphorylated human phospholamban pentamer, PDB id: 2HYN. (d) Phospholamban restraint satisfaction score vs. packing score for all structures. The vertical and horizontal lines indicate the cutoffs for WPS structures: 1 Å for the satisfaction score and 0 kcal/mol for the packing score. The green stars and the blue crosses indicate the set of satisfying structures. The magenta points indicate the set of nonsatisfying structures that have been pruned. The green stars indicate the set of WPS structures and the red star indicates the reference structure [117].

Using equation (18.13), the algorithm computes redundant and inconsistent NOEs and assignments, via unions and intersections of geometric sets in SCS. Let Q⊂RQ \subset R be a set of NOEs. Let rkr_k be an (arbitrary) ambiguous NOE (not in QQ) with tkt_k assignments. We compute that NOE assignment rklr_{kl} is redundant with respect to QQ if and only if p(Q)⊂sklp(Q) \subset s_{kl} . Similarly, we compute that rklr_{kl} is inconsistent with respect to QQ if and only if p(Q)∩skl=∅p(Q) \cap s_{kl} = \emptyset , where ∅\emptyset is the empty set. We can extend these algorithms from assignments to NOEs as follows. Let Sk=⋃l=1tksklS_k = \bigcup_{l=1}^{t_k} s_{kl} be the region of the SCS that satisfies at least one assignment of rkr_k . We then compute that rkr_k is redundant with respect to QQ if and only if p(Q)⊂Skp(Q) \subset S_k , and compute that rkr_k is inconsistent with respect to QQ if and only if p(Q)∩Sk=∅p(Q) \cap S_k = \emptyset . SYMBRANE eliminates inconsistent NOEs and assignments, and is able to detect redundant ones. SYMBRANE’s approach to identifying the mutually consistent, complete set of NOE assignments and SCS regions is summarized in figure 18.3 and described in detail in Potluri et al. [118].

When RDCs can be obtained in combination with NOEs, structure determination of symmetric homooligomers reduces to an inverse kinematics problem that can be solved exactly (analogously to the procedures in section 17.1), without resorting to the branch-and-bound search used in studies by Potluri et al. [117, 118]. It is likely that ambiguous NOE assignment [118] will also be improved since the ensemble of exact solutions will be smaller, increasing the structural precision that geometrically prunes the assignments. SYMBRANE currently allows for limited uncertainty in the subunit structure: SYMBRANE computes satisfying structures using rigid monomers, but energy scores allowing side-chain minimization [117]. This allows for some side-chain flexibility, but is subject to local minima and is not systematic. Instead, one could use a rotamer library to systematically sample different distinct conformational side-chain states, exploiting recent advances in rotamer optimization [88, 45, 44], particularly in the presence of provable rotamer energy minimization [45, 44]. Considering rotamers increases the complexity of the hierarchical subdivision scheme, but techniques such as dead-end elimination (DEE) [34, 85, 48, 115, 44] and minimized-DEE [45, 44] can be used to prune rotamers and compute solutions more quickly. It may also be possible to derive exact or analytic solutions for NOE assignment when RDCs are available. While more difficult, backbone flexibility could also be incorporated in a DEE-like search [42, 43]. Allowing greater uncertainty in the subunit structure would make SYMBRANE more robust and eventually useful for multimers with a more intricate folding topology.

Two novel features of SYMBRANE are of particular note: (1) the ability to assign intersubunit NOEs in a complete search that avoids exhaustive, exponential enumeration [118]; and (2) the ability to determine the oligomeric number using NMR data alone [117]. Specifically:

  1. Errors in resolving intersubunit NOE ambiguities have led to incorrect NMR structures [20]. Beyond the importance of this particular problem in NMR data analysis, SYMBRANE represents a departure from the stochastic methods frequently employed by the NMR community. A corollary is that such stochastic methods, now routinely employed, should be reconsidered in light of their inability to ensure identification of the unique or globally optimal structural models consistent with a set of NMR observations. SYMBRANE can provide more confident answers to these problems.

Figure 18.3 SYMBRANE strategy to resolve ambiguous NOEs in structure determination of symmetric homo-oligomers. Top: Different possible assignments for one ambiguous NOE are illustrated for a trimer. The NOE could be ordered between subunits as 1-2-3 or 1-3-2, and has chemical shift degeneracy between protons a, b, and c. The former is called “subunit ambiguity” and the latter “atom ambiguity.” Phase 1: Consistent regions in the SCS are obtained using a branch-and-bound algorithm [117], taking a subset of available NOEs (typically atom-unambiguous NOEs, if any) as input. The 4-dimensional SCS is cartoon-represented as in figure 18.2b. Phase 2: SYMBRANE uses the consistent regions output from the branch-and-bound search plus possible assignments of the ambiguous NOEs, to determine a mutually consistent, complete set of NOE assignments and ambiguity consistent regions (ACR) in SCS. On p. 177: Pseudocode for SYMBRANE’s ambiguity resolution algorithm. Each NOE’s score is the average of the scores of all of its possible assignments (the line marked (*), bottom). This score provides an ordering criterion for NOE assignment. Potluri et al. [118] showed that the order does not affect the completeness, results, or accuracy, but can improve the efficiency.

  1. In general, the oligomeric state of the complex includes the symmetry type (CnC_n , DnD_n , etc.) as well as the oligomeric number (n=2,3,4,…n = 2, 3, 4, \dots). In addition to assigning the intermolecular NOEs and determining the complex structure, SYMBRANE tests whether the available data suffices to determine the oligomeric number for CnC_n symmetry. For each possible symmetry type and oligomeric number, SYMBRANE can determine a set YY of WPS structures. For some oligomeric states, Y=∅Y = \emptyset : we can place higher confidence on the oligomeric state that (a) has some WPS structures (i.e., Y≠∅Y \neq \emptyset), and (b) affords better vdW packing. Thus, we can determine the oligomeric state using the NMR data and vdW packing. SYMBRANE provides for an independent verification of the oligomeric state (which is typically determined using experiments such as chemical cross-linking

Input: RR : Set of NOEs

U⊂RU \subset R : Subset of the NOEs (typically atom-unambiguous NOEs)

CC : Set of cells from branch-and-bound with UU

NN : R→ℤn−1×AR \rightarrow \mathbb{Z}_{n-1} \times A : Possible assignments for each NOE due to subunit ambiguity (subunit offset 1 to n−1n-1)

and atom ambiguity (proton in the set AA).

Output: C′⊂CC' \subset C : Remaining cells

N′⊂NN' \subset N : Remaining assignments

Algorithm:initialize R′←R−UR' \leftarrow R - U , C′←CC' \leftarrow C while R′≠∅R' \neq \emptyset

// Determine the next NOE to assign according to our criterion

S←S \leftarrow representative structures for C′C'

q←arg⁡max⁡r∈R′a∈N(r){s∈S∣r under assignment a is violated in s}(*)q \leftarrow \arg \max_{\substack{r \in R' \\ a \in N(r)}} \{s \in S \mid r \text{ under assignment } a \text{ is violated in } s\} \quad (*)

R′←R′−{q}R' \leftarrow R' - \{q\}

// Remove inconsistent cells

C′←{c∈C′∣∃a∈N(q) s.t. c is consistent with q under assignment a}C' \leftarrow \{c \in C' \mid \exists a \in N(q) \text{ s.t. } c \text{ is consistent with } q \text{ under assignment } a\} end while

// Remove inconsistent assignments

N′←{(r,a)∣r∈R,a∈N(r),∃c∈C′ s.t. c is consistent with r under assignment a}N' \leftarrow \{(r, a) \mid r \in R, a \in N(r), \exists c \in C' \text{ s.t. } c \text{ is consistent with } r \text{ under assignment } a\} return N′N' , C′C' followed by SDS-PAGE, or by equilibrium sedimentation). The results from SYMBRANE show how novel algorithms can draw conclusions from NMR data that were previously possible only using additional biophysical experiments. Such algorithms can reduce experimental time and provide cross-validation of structure and assembly.

Figure 18.3 (Continued)

References

  • [1] A. B. Eiso, D. J. R. Pugh, R. Kaptein, R. Boelens, and A. M. J. J. Bonvin. Direct use of unassigned resonances in NMR structure calculations with proxy residues. Journal of the American Chemical Society, 128;23(2006):7566–7571.
  • [2] H. M. Al-Hashimi, P. J. Bolon, and J. H. Prestegard. Molecular symmetry as an aid to geometry determination in ligand protein complexes. Journal of Magnetic Resonance, 142(2000):153–158.
  • [3] H. M. Al-Hashimi, A. Gorin, A. Majumdar, Y. Gosser, and D. J. Patel. Towards structural genomics of RNA: Rapid NMR resonance assignment and simultaneous RNA tertiary structure determination using residual dipolar couplings. Journal of Molecular Biology, 318(2002):637–649.

[4] H. M. Al-Hashimi and D. J. Patel. Residual dipolar couplings: Synergy between NMR and structural genomics. Journal of Biomolecular NMR 22;1(2002):1–8.

[5] A. C. Anderson. Two crystal structures of dihydrofolate reductase-thymidylate synthase from Cryptosporidium hominis reveal protein-ligand interactions including a structural basis for observed antifolate resistance. Acta Crystallographica, Section F, Structural Biology and Crystallization Communications 61;3(2005):258–262.

[6] M. Andrec, P. Du, and R. M. Levy. Protein backbone structure determination using only residual dipolar couplings from one ordering medium. Journal of Biomolecular NMR 21;4(2001):335–347.

[7] A. Annila, H. Aitio, E. Thulin, and T. Drakenberg. Recognition of protein folds via dipolar couplings. Journal of Biomolecular NMR 14(1999):223–230.

[8] S. Apaydin, V. Conitzer, and B. R. Donald. Structure-based protein NMR assignments using native structural ensembles. Journal of Biomolecular NMR 40(2008):263–276.

[9] P. J. Artymiuk, C. C. F. Blake, D. W. Rice, and K. S. Wilson. The structures of the monoclinic and orthorhombic forms of hen egg-white lysozyme at 6 angstroms resolution. Acta Crystallographica, Section B Biology Crystallographica 38(1982):778.

[10] C. R. Babu, P. F. Flynn, and A. J. Wand. Validation of protein structure from preparations of encapsulated proteins dissolved in low viscosity fluids. Journal of the American Chemical Society, 123(2001):2691.

[11] C. Bailey-Kellogg, J. J. Kelley III, R. Lilien, and B. R. Donald. Physical geometric algorithms for structural molecular biology; in the Special Session on Computational Biology & Chemistry, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA-2001), May 2001, pp. 940–947.

[12] C. Bailey-Kellogg, A. Widge, J. J. Kelley III, M. J. Berardi, J. H. Bushweller, and B. R. Donald. The NOESY Jigsaw: Automated protein secondary structure and main-chain assignment from sparse, unassigned NMR data. Journal of Computational Biology 3-4;7(2000):537–558.

[13] B. E. Coggins and P. Zhou. Sampling of the NMR time domain along concentric rings. Journal of Magnetic Resonance 184;2(2007):207–221.

[14] B. Berger, J. Kleinberg, and F. T. Leighton. Reconstructing a three-dimensional model with arbitrary errors. Journal of the ACM, 46;2(1999):212–235.

[15] A. T. Brünger. XPLOR: A System for X-ray Crystallography and NMR. New Haven, CT: Yale University Press, 1993.

[16] J. Cavanaugh, W. J. Fairbrother, A. G. Palmer III, and N. J. Skelton. Protein NMR Spectroscopy: Principles and Practice. New York: Academic Press, 1995.

[17] C. N. Cavasotto, J. A. Kovacs, and R. A. Abagyan. Representing receptor flexibility in ligand docking through relevant normal modes. Journal of the American Chemical Society 127;26(2005):9632–9640.

[18] Y. Chen, J. Reizer, M. H. Saier Jr., W. J. Fairbrother, and P. E. Wright. Mapping of the binding interfaces of the proteins of the bacterial phosphotransferase system, HPr and IIAglc. Biochemistry 32;1(1993):32–37.

[19] J. J Chou, S. Li, and A. Bax. Study of conformational rearrangement and refinement of structural homology models by the use of heteronuclear dipolar couplings. Journal of Biomolecular NMR 18(2000):217–227.

[20] G. M. Clore, J. G. Omichinski, K. Sakaguchi, N. Zambrano, H. Sakamoto, E. Appella, and A. M. Gronenborn. Interhelical angles in the solution structure of the oligomerization domain of p53: Correction. Science 267;5203(1995):1515–1516.

[21] B. E. Coggins, R. A. Venters, and P. Zhou. Filtered backprojection for the reconstruction of a high-resolution (4,2)D CH3-NH NOESY spectrum on a 29 kDa protein. Journal of the American Chemical Society 127;33(2005):11562–11563.

[22] B. E. Coggins and P. Zhou. PACES: Protein sequential assignment by computer-assisted exhaustive search. Journal of Biomolecular NMR 26;2(2003):93–111.

[23] B. E. Coggins and P. Zhou. Polar Fourier transforms of radially sampled NMR data. Journal of Magnetic Resonance 182;1(2006):84–95.

[24] F. Cordier, M. Rogowski, S. Grzesiek, and A. Bax. Observation of through-hydrogen-bond 2hJHC in a perdeuterated protein. Journal of Magnetic Resonance 40;2(1999):510–512.

[25] G. Cornilescu, F. Delaglio, and A. Bax. Protein backbone angle restraints from searching a database for chemical shift and sequence homology. Journal of Biomolecular NMR 13(1999):289–302.

[26] E. A. Coutsias, C. Seok, M. P. Jacobson, and K. A. Dill. A kinematic view of loop closure. Journal of Computational Chemistry 25;4(2004):510–528.

[27] E. A. Coutsias, C. Seok, M. J. Wester, and K. A. Dill. Resultants and loop closure. International Journal of Quantum Chemistry 106;1(2006):176–189.

[28] G. Crippen. Chemical distance geometry: Current realization and future projection. Journal of Mathematical Chemistry 6(1991):307–324.

[29] G. M. Crippen and T. F. Havel. Distance Geometry and Molecular Conformations. New York: John Wiley, 1988.

[30] A. D. J. Cross and E. R. Hancock. Graph matching with a dual-step EM algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20;11(1998):1236–1253.

[31] F. del Rio-Portílla, V. Blechta, and R. Freeman. Measurement of poorly-resolved splittings by J-doubling in the frequency domain. Journal of Magnetic Resonance 111a(1994):132–135.

[32] F. Delaglio, G. Kontaxis, and A. Bax. Protein structure determination using molecular fragment replacement and NMR dipolar couplings. Journal of the American Chemical Society, 122;9(2000):2142–2143.

[33] A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39;1(1977):1–38.

[34] J. Desmet, M. DeMaeyer, B. Hazes, and I. Lasters. The dead-end elimination theorem and its use in protein side-chain positioning. Nature, 356(1992):539–542.

[35] R. Diamond. Real-space refinement of the structure of hen egg-white lysozyme. Journal of Molecular Biology, 82(1974):371–391.

[36] B. R. Donald. Plenary lecture: Algorithmic challenges in structural molecular biology and proteomics, in Proceedings of the Sixth International Workshop on the Algorithmic Foundations of Robotics (WAFR). Utrecht/Zeist, The Netherlands: July 2004, pp. 1–10. University of Utrecht. in Algorithmic Foundations of Robotics VI, Springer Tracts in Advanced Robotics (Vol. 17), M. Erdmann, M. Overmars, D. Hsu, and A. F. van der Stappen (eds.). Berlin: Springer, 2005, pp. 1–10.

[37] B. R. Donald, D. Kapur, and J. Mundy. Symbolic and Numerical Computation for Artificial Intelligence. London: Academic Press, Harcourt Jovanovich, 1992.

[38] A. C. Fowler, F. Tian, H. M. Al-Hashimi, and J. H. Prestegard. Rapid determination of protein folds using residual dipolar couplings. Journal of Molecular Biology 304;3(2000):447–460.

[39] T. Gallagher, P. Alexander, P. Bryan, and G. L. Gilliland. Two crystal structures of the B1 immunoglobulin-binding domain of streptococcal protein G and comparison with NMR. Biochemistry, 33(1994):4721–4729.

[40] K. H. Gardner and L. E. Kay. Production and incorporation of 15N^{15}\text{N} , 13C^{13}\text{C} , 2H^2\text{H} (1H^1\text{H} - δ\delta 1 methyl) isolucine into proteins for multidimensional NMR studies. Journal of the American Chemical Society 119;32(1997):7599–7600.

[41] G. Gemmecker, W. Jahnke, and H. Kessler. Measurement of fast proton exchange rates in isotopically labelled compounds. Journal of American Chemical Society 115;24(1993):11620–11621.

[42] I. Georgiev and B. R. Donald. Dead-end elimination with backbone flexibility. Bioinformatics, 23(13), 2007. Special issue on papers from the International Conference on Intelligent Systems for Molecular Biology (ISMB 2007), Vienna, Austria: July 21–25, 2007.

[43] I. Georgiev, D. Keedy, J. Richardson, D. Richardson, and B. R. Donald. Algorithm for backrub motions in protein design. Bioinformatics, 22 (Jul 2008):e174–183. Special issue on papers from International Conference on Intelligent Systems for Molecular Biology (ISMB 2008), Toronto, CA, July 2008.

[44] I. Georgiev, R. Lilien, and B. R. Donald. Improved pruning algorithms and divide-and-conquer strategies for dead-end elimination, with application to protein design. Bioinformatics 22;14(2006):e174–183. Special issue on papers from the International Conference on Intelligent Systems for Molecular Biology (ISMB 2006), Fortaleza, Brazil.

[45] I. Georgiev, R. Lilien, and B. R. Donald. The minimized dead-end elimination criterion and its application to protein redesign in a hybrid scoring and search algorithm for computing partition functions over molecular ensembles. Journal of Computational Chemistry 29;10(2008):1527–1542.

[46] A. W. Giesen, S. W. Homans, and J. M. Brown. Determination of protein global folds using backbone residual dipolar coupling and long-range NOE restraints. Journal of Biomolecular NMR 25(2003):63–71.

[47] E. Girard, L. Chantalat, J. Vicat, and R. Kahn. Gd-HPDO3A, a complex to obtain high-phasing-power heavy atom derivatives for SAD and MAD experiments: Results with tetragonal hen egg-white lysozyme. Acta Crystallographica, Section D, Biological Crystallography 58(2001):1–9.

[48] R. Goldstein. Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophysical Journal 66(1994):1335–1340.

[49] M. J. Gorczynski, J. Grembecka, Y. Zhou, Y. Kong, L. Roudaiya, M. G. Douvas, et al. Allosteric inhibition of the protein-protein interaction between the leukemia-associated proteins RUNX1 and CBF β\beta . Chemistry & Biology 14;10(2007).

[50] A. M. Gronenborn, D. R. Filpula, N. Z. Essig, A. Achari, M. Whitlow, P. T. Wingfield, and G. M. Clore. A novel, highly stable fold of the immunoglobulin binding domain of streptococcal protein G. Science 253(1991):657.

[51] S Grzesiek and A Bax. Measurement of amide proton exchange rates and NOEs with water in 13C/15N-enriched calcineurin B. Journal of Biomolecular NMR, 3(6)(1993)627–638.

[52] P. Güntert, C. Mumenthaler, and K. Wüthrich. Torsion angle dynamics for NMR structure calculation with the new program DYANA. Journal of Molecular Biology 273(1997):283–298.

[53] Peter Guntert. Automated NMR structure calculation with CYANA. Methods in Molecular Biology 278(2004):353–378.

[54] P. J. Hajduk, R. P. Meadows, and S. W. Fesik. Drug design: Discovering high-affinity ligands for proteins. Science 278(1997):497–499.

[55] B. Hendrickson. Conditions for unique graph realizations. SIAM Journal on Computing 21(1992):65–84.

[56] B. Hendrickson. The molecule problem: Exploiting structures in global optimization. SIAM Journal on Optimization 5(1995):835–857.

[57] T. Herrmann, P. Güntert, and K. Wüthrich. Protein NMR structure determination with automated NOE assignment using the new software CANDID and the torsion angle dynamics algorithm DYANA. Journal of Molecular Biology, 319(2002):209–227.

[58] K. Hinsen. Normal mode theory and harmonic potential approximations. Course and Lecture Notes. Available at http://dirac.cnrs-orleans.fr/~hinsen/, Centre de Biophysique Moléculaire (CNRS), Orleans, France, 2000.

[59] Y. J. Huang, G. V. Swapna, P. K. Rajan, H. Ke, B. Xia, K. Shukla, et al. Solution NMR structure of ribosome-binding factor a (RbfA), a cold shock adaptation protein from Escherichia coli. Journal of Molecular Biology, 327(2003):521–536.

[60] Y.J. Huang, R. Tejero, R. Powers, and G.T. Montelione. A topology-constrained distance network algorithm for protein structure determination from NOESY data. Proteins 62;3(2006):587–603.

[61] J.-C. Hus, D. Marion, and M. Blackledge. De novo determination of protein structure by NMR using orientational and long-range order restraints. Journal of Molecular Biology, 298;5(2000):927–936.

[62] J. C. Hus, D. Marion, and M. Blackledge. Determination of protein backbone using only residual dipolar couplings. Journal of the American Chemical Society 123(2001):1541–1542.

[63] J.C. Hus, J. Prompers, and R. Brüschweiler. Assignment strategy for proteins of known structure. Journal of Magnetic Resonance 157(2002):119–125.

[64] J. Korukottu, M. Bayrhuber, P. Montaville, V. Vijayan, Y. S. Jung, S. Becker, and M. Zweckstetter. Fast high-resolution protein structure determination by using unassigned NMR data. Angewandte Chemie (International Edition in English), 46(2007):1176–1179.

[65] D. J. Jacobs, A. J. Rader, L. A. Kuhn, and M. F. Thorpe. Protein flexibility predictions using graph theory. Proteins 44;2(2001):150–165.

[66] E. C. Johnson, G. A. Lazar, J. R. Desjarlais, and T. M. Handel. Solution structure and dynamics of a designed hydrophobic core variant of ubiquitin. Structure Folding Design, 7(1999):967–976.

[67] Y.S. Jung and M. Zweckstetter. Backbone assignment of proteins with known structure using residual dipolar couplings. Journal of Biomolecular NMR 30;1(2004):25–35.

[68] K. Juszewski, C. D. S. Schwieters, D. S. Garrett, R. A. Byrd, N. Tjandra, and G. M. Clore. Completely automated, highly error-tolerant macromolecular structure determination from multidimensional nuclear Overhauser enhancement spectra and chemical shift assignments. Journal of the American Chemical Society 126(2004):6258–6273.

[69] K. Ruan, K. B. Briggman, and J. R. Tolman. De novo determination of internuclear vector orientations from residual dipolar couplings measured in three independent alignment media. Journal of Biomolecular NMR 41;2(2008):61–76.

[70] H. Kamisetty, C. Bailey-Kellogg, and G. Pandurangan. An efficient randomized algorithm for contact-based NMR backbone resonance assignment. Bioinformatics 22;2(2006):172–180.

[71] L. E. Kay. Protein dynamics from NMR. Nature Structural Biology 5(1998):513–517.

[72] M. D. Kemple, B. D. Ray, K. B. Lipkowitz, F. G. Prendergast, and B. D. Rao. The use of lanthanides for solution structure determination of biomolecules by NMR: Evaluation of the methodology with EDTA derivatives as model systems. Journal of the American Chemical Society 110;25(1988):8275–8287.

[73] D. E. Kim, D. Chivian, and D. Baker. Protein structure prediction and analysis using the Robetta server. Nucleic Acids Research 32(Web Server issue)(2004):526–531.

[74] R. Kolodny, L. Guibas, M. Levitt, and P. Koehl. Inverse kinematics in biology: The protein loop closure problem. The International Journal of Robotics Research 24(2005):151–163.

[75] R. J. Kovacs, M. T. Nelson, H. K. Simmerman, and L. R. Jones. Phospholamban forms Ca2+\text{Ca}^{2+} -selective channels in lipid bilayers. The Journal of Biological Chemistry 263(1988):18364–18368.

[76] H. W. Kuhn. Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1955):83–97.

[77] I. V. Kurinov and R. W. Harrison. The influence of temperature on lysozyme crystals—structure and dynamics of protein and water. Acta Crystallographica, Section D, Biological Crystallography 51(1995):98–109.

[78] C. Langmead and B. R. Donald. 3D structural homology detection via unassigned residual dipolar couplings, in Proceedings of the IEEE Computer Society Bioinformatics Conference (CSB), pp. 209–217, Stanford, August 2003. PMID: 16452795.

[79] C. Langmead and B. R. Donald. An expectation/maximization nuclear vector replacement algorithm for automated NMR resonance assignments. Journal of Biomolecular NMR 29;2(2004):111–138.

[80] C. Langmead and B. R. Donald. High-throughput 3D structural homology detection via NMR resonance assignment, in Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB), pp. 278–289, Stanford, CA, August 2004. PMID: 16448021.

[81] C. Langmead, C. R. McClung, and B. R. Donald. A maximum entropy algorithm for rhythmic analysis of genome-wide expression patterns, in Proceedings of the IEEE Computer Society Bioinformatics Conference (IEEE CSB), pp. 237–245, August 2002. PMID: 15838140.

[82] C. Langmead, A. Yan, R. Lilien, L. Wang, and B. R. Donald. A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments; in Proceedings of The Seventh Annual International Conference on Research in Computational Molecular Biology (RECOMB), pp. 176–187, Berlin, Germany, April 2003. ACM Press.

[83] C. Langmead, A. Yan, R. Lilien, L. Wang, and B. R. Donald. A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments. Journal of Computational Biology 11;2–3(2004):277–298.

[84] C. Langmead, A. Yan, C. R. McClung, and B. R. Donald. Phase-independent rhythmic analysis of genome-wide expression patterns. Journal of Computational Biology 10;3–4(2003):521–536.

[85] I. Lasters and J. Desmet. The fuzzy-end elimination theorem: Correctly implementing the side chain placement algorithm based on the dead-end elimination theorem. Protein Engineering 6(1993):717–722.

[86] M. Li, H. P. Phatnani, Z. Guan, H. Sage, A. L. Greenleaf, and P. Zhou. Solution structure of the Set2-Rpb1 interacting domain of human Set2 and its interaction with the hyperphosphorylated C-terminal domain of Rpb1. Proceedings of the National Academy of Sciences (U S A) 102;49(2005):17636–17641.

[87] R. Lilien, H. Farid, and B. R. Donald. Probabilistic disease classification of expression-dependent proteomic data from mass spectrometry of human serum. Journal of Computational Biology 10;6(2003):925–946.

[88] R. Lilien, B. Stevens, A. Anderson, and B. R. Donald. A novel ensemble-based scoring and search algorithm for protein redesign, and its application to modify the substrate specificity of the Gramicidin Synthetase A phenylalanine adenylation enzyme. Journal of Computational Biology, 12;6–7(2005):740–761.

[89] R. H. Lilien, C. Bailey-Kellogg, A. C. Anderson, and B. R. Donald. A subgroup algorithm to identify cross-rotation peaks consistent with non-crystallographic symmetry. Acta Crystallographica Section D, Biological Crystallography 60;6(2004):1057–1067.

[90] K. Lim, A. Nadarajah, E. L. Forsythe, and M. L. Pusey. Locations of bromide ions in tetragonal lysozyme crystals. Acta Crystallographica, Section D, Biological Crystallography 54(1998):899–904.

[91] B Lopez-Mendez and P Guntert. Automated protein structure determination from NMR spectra. Journal of the American Chemical Society, 128;40(2006):13112–13122.

[92] J. A. Losonczi, M. Andrec, M. W. Fischer, and J. H. Prestegard. Order matrix analysis of residual dipolar couplings using singular value decomposition. Journal of Magnetic Resonance 138;2(1999):334–342.

[93] M. Bryson, F. Tian, J. H. Prestegard, and H. Valafar. REDCRAFT: A tool for simultaneous characterization of protein backbone structure and motion from RDC data. Journal of Magnetic Resonance 191;2(2008):322–334.

[94] A. Marin, T. E. Malliavin, P. Nicolas, and M. A. Delsuc. From NMR chemical shifts to amino acid types: Investigation of the predictive power carried by nuclei. Journal of Biomolecular NMR 30;1(2004):47–60.

[95] J. Meiler, N. Blomberg, M. Nilges, and C. Griesinger. A new approach for applying residual dipolar couplings as restraints in structure elucidation. Journal of Biomolecular NMR 16(2000):245–252.

[96] J. Meiler, W. Peti, and C. Griesinger. DipoCoup: A versatile program for 3D-structure homology comparison based on residual dipolar couplings and pseudocontact shifts. Journal of Biomolecular NMR 17(2000):283–294.

[97] J. Meiler and D. Baker. Rapid protein fold determination using unassigned NMR data. Proceedings of the National Academy of Sciences (U S A) 100;26(2003):15404–15409.

[98] J. Meiler and D. Baker. The fumarate sensor DcuS: Progress in rapid protein fold elucidation by combining protein structure prediction methods with NMR spectroscopy. Journal of Magnetic Resonance 173;2(2005):310–316.

[99] R. Mettu, R. Lilien, and B. R. Donald. High-throughput inference of protein-protein interfaces from unassigned NMR data. Bioinformatics 21;Suppl. 1(2005):i292–i301.

[100] G A Mueller, W. Y. Choy, D. Yang, J. D. Forman-Kay, R. A. Venters, and L. E. Kay. Global folds of proteins with low densities of NOEs using residual dipolar couplings: Application to the 370-residue maltodextrin-binding protein. Journal of Molecular Biology 300;1(2000):197–212.

[101] S Neal, A. M. Nip, H. Zhang, and D. S. Wishart. Rapid and accurate calculation of protein 1H^1\text{H} , 13C^{13}\text{C} and 15N^{15}\text{N} chemical shifts. Journal of Biomolecular NMR 26(2003):215–240.

[102] M. Nilges. A calculation strategy for the structure determination of symmetric dimers by 1H^1\text{H} NMR. Proteins 17;3(1993):297–309.

[103] M. Nilges, M. Macias, S. Odonoghue, and H. Oschkinat. Automated NOESY interpretation with ambiguous distance restraints: The refined NMR solution structure of the pleckstrin homology domain from β\beta -spectrin. Journal of Molecular Biology 269(1997):408–422.

[104] K. Noonan, D. O’Brien, and J. Snoeyink. Probik: protein backbone motion by inverse kinematics. International Journal of Robotics Research 24;11(2005):971–982.

[105] O. Vitek, C. Bailey-Kellogg, B. Craig, and J. Vitek. Inferential backbone assignment for sparse data. Journal of Biomolecular NMR 35;3(2006):187–208.

[106] H. Oki, Y. Matsuura, H. Komatsu, and A. A. Chernov. Refined structure of orthorhombic lysozyme crystallized at high temperature: Correlation between morphology and intermolecular contacts. Acta Crystallographica, Section D, Biological, Crystallography 55(1999):114.

[107] A.L. Okorokov, M.B. Sherman, C. Plisson, V. Grinkevich, K. Sigmundsson, G. Selivanova, et al. The structure of p53 tumour suppressor protein reveals the basis for its functional plasticity. EMBO Journal 25;21(2006):5191–5200.

[108] E. T. Olejniczak, R. X. Xu, and S. W. Fesik. A 4D HCCH-TOCSY experiment for assigning the side-chain 1H^1\text{H} and 13C^{13}\text{C} resonances of proteins. Journal of Biomolecular NMR 2;6(1992):655–659.

[109] R. O’Neil, R. Lilien, B. R. Donald, R. Stroud, and A. Anderson. The crystal structure of dihydrofolate reductase-thymidylate synthase from Cryptosporidium hominis reveals a novel architecture for the bifunctional enzyme. The Journal of Eukaryotic Microbiology 50;6(2003):555–556.

[110] R. O’Neil, R. Lilien, B. R. Donald, R. Stroud, and A. Anderson. Phylogenetic classification of protozoa based on the structure of the linker domain in the bifunctional enzyme, dihydrofolate reductase-thymidylate synthase. Journal of Biological Chemistry 278;52(2003):52980–52987.

[111] K. Oxenoid and J. J. Chou. The structure of phospholamban pentamer reveals a channel-like architecture in membranes. Proceedings of the National Academy of Sciences (U S A) 102(2005):10870–10875.

[112] A. G. Palmer. Probing Molecular Motion By NMR. Current Opinion in Structural Biology 7(1997):732–737.

[113] A. G. Palmer, J. Williams, and A. McDermott. Nuclear magnetic resonance studies of biopolymer dynamics. Journal of Physical Chemistry 100(1996):13293–13310.

[114] D. A. Pearlman, D. A. Case, J. W. Caldwell, W. S. Ross, T. E. Cheatham, S. DeBolt, et al. AMBER, a package of computer programs for applying molecular mechanics, normal mode analysis, molecular dynamics and free energy calculations to simulate the structures and energies of molecules. Computer Physics Communications 91(1995):1–41.

[115] N. Pierce, J. Spriet, J. Desmet, and S. Mayo. Conformational splitting: A more powerful criterion for dead-end elimination. Journal of Computational Chemistry 21(2000):999–1009.

[116] V. M. Popov, D. C. M. Chan, Y. A. Fillingham, W. A. Yee, D. L. Wright, and A. C. Anderson. Analysis of complexes of inhibitors with Cryptosporidium hominis DHFR leads to a new trimethoprim derivative. Bioorganic Medicinal Chemistry Letters 16;16(2006):4366–4370.

[117] S. Potluri, A. Yan, , J. J. Chou, B. R. Donald, and C. Bailey-Kellogg. Structure determination of symmetric homo-oligomers by a complete search of symmetry configuration space using NMR restraints and van der Waals packing. Proteins: Structure, Function and Bioinformatics 65;1(2006):203–219.

[118] S. Potluri, A. Yan, B. R. Donald, and C. Bailey-Kellogg. A complete algorithm to resolve ambiguity for inter-subunit NOE assignment in structure determination of symmetric homo-oligomers. Protein Science 16;1(2006).

[119] J. H. Prestegard. New techniques in structural NMR—anisotropic interactions. Nature Structural Biology, (1998):517–522.

[120] J. H. Prestegard, C. M. Bougault, and A. I. Kishore. Residual dipolar couplings in structure determination of biomolecules. Chemical Reviews 104;8(2004):3519–3540.

[121] Y. Qu, J. T. Guo, V. Olman, and Y. Xu. Protein fold recognition through application of residual dipolar coupling data. Pacific Symposium on Biocomputing, (2004):459–470.

[122] R. Bertram, J. R. Quine, M. S. Chapman, and T. A. Cross. Atomic refinement using orientational restraints from solid-state NMR. Journal of Magnetic Resonance 147(2000):9–16.

[123] R. Ramage, J. Green, T. W. Muir, O. M. Ogunjobi, S. Love, and K. Shaw. Synthetic, structural and biological studies of the ubiquitin system: The total chemical synthesis of ubiquitin. Journal of Biochemistry 299(1994):151–158.

[124] W. Rieping, M. Habeck, and M. Nilges. Inferential structure determination. Science 209;5732(2005):303–306.

[125] C. A. Rohl and D. Baker. De Novo determination of protein backbone structure from residual dipolar couplings using Rosetta. Journal of the American Chemical Society 124;11(2002):2723–2729.

[126] C. A. Rohl. Protein structure estimation from minimal restraints using Rosetta. Methods in Enzymology 394(2005):244–260.

[127] K. Ruan and J. R. Tolman. Composite alignment media for the measurement of independent sets of NMR residual dipolar couplings. Journal of the American Chemical Society 127;43(2005):15032–15033.

[128] S. Bansal, X. Miao, M.W. Adams, J. H. Prestegard, and H. Valafar. Rapid classification of protein structure models using unassigned backbone RDCs and probability density profile analysis (PDPA). Journal of Magnetic Resonance 192;1(2008):60–68.

[129] S. Rumpel, S. Becker, and M. Zweckstetter. High-resolution structure determination of the CyIR2 homodimer using paramagnetic relaxation enhancement and structure-based prediction of molecular alignment. Journal of Biomolecular NMR 40;1(2008):1–13.

[130] A. Saupe. Recent results in the field of liquid crystals. Angewandte Chemie 7(1968):97–112.

[131] J. B. Saxe. Embeddability of weighted graphs in kk -space is strongly NP-hard, in Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, (1979):480–489.

[132] B. R. Seavey, E. A. Farr, W. M. Westler, and J. L. Markley. A relational database for sequence-specific protein NMR data. Journal of Biomolecular NMR 1(1991):217–236.

[133] S. B. Shuker, P. J. Hajduk, R. P. Meadows, and S. W. Fesik. Discovering high-affinity ligands for proteins: SAR by NMR. Science 274(1996):1531–1534.

[134] R. Singh and B. Berger. ChainTweak: Sampling from the neighbourhood of a protein conformation. Pacific Symposium on Biocomputing 2005 (2005):54–65.

[135] N. R. Skrynnikov and L. E. Kay. Assessment of molecular structure using frame-independent orientational restraints derived from residual dipolar couplings. Journal of Biomolecular NMR 18;3(2000):239–252.

[136] B. Stevens, R. Lilien, I. Georgiev, B. R. Donald, and A. Anderson. Redesigning the PheA domain of Gramicidin Synthetase leads to a new understanding of the enzyme’s mechanism and selectivity. Biochemistry 45;51(2006):15495–15504.

[137] K. Suhre and Y.H. Sanejouand. ElNemo: A normal mode web server for protein movement analysis and the generation of templates for molecular replacement. Nucleic Acids Research 32(Web Server issue)(2004):610–614.

[138] K. Suhre and Y. H. Sanejouand. On the potential of normal-mode analysis for solving difficult molecular-replacement problems. Acta Crystallographica, Section D, Biological Crystallography 60;Pt 4(2004):796–799.

[139] F. Tian, H. Valafar, and J. H. Prestegard. A dipolar coupling based strategy for simultaneous resonance assignment and structure determination of protein backbones. Journal of the American Chemical Society 123;47(2001):11791–11796.

[140] N. Tjandra and A. Bax. Direct measurement of distances and angles in biomolecules by NMR in a dilute liquid crystalline medium. Science 278(1997):1111–1114.

[141] D. Tobi and I. Bahar. Structural changes involved in protein binding correlate with intrinsic motions of proteins in the unbound state. Proceedings of the National Academy of Sciences (U S A) 102;52(2005):18908–18913.

[142] J. R. Tolman, J. M. Flanagan, M. A. Kennedy, and J. H. Prestegard. Nuclear magnetic dipole interactions in field-oriented proteins: Information for structure determination in solution. Proceedings of the National Academy of Sciences USA 92(1995):9279–9283.

[143] V. Tugarinov, W. Y. Choy, V. Y. Orekhov, and L. E. Kay. Solution NMR-derived global fold of a monomeric 82-kDa enzyme. Proceedings of the National Academy of Sciences of the United States 102;3(2005):622–627.

[144] V. Tugarinov, R. Muhandiram, A. Ayed, and L. E. Kay. Four-dimensional NMR spectroscopy of a 723-residue protein: Chemical shift assignments and secondary structure of malate synthase G. Journal of the American Chemical Society 124;34(2002):10025–10035.

[145] H. Valafar and J. H. Prestegard. Rapid classification of a protein fold family using a statistical analysis of dipolar couplings. Bioinformatics 19;12(2003):1549–1555.

[146] M. C. Vaney, S. Maignan, M. Ries-Kautt, and A. Ducruix. High-resolution structure (1.33 Angstrom) of a HEW lysozyme tetragonal crystal grown in the APCF apparatus. Data and structural comparison with a crystal grown under microgravity from SpaceHab-01 mission. Acta Crystallographica, Section D, Biological Crystallography 52(1996):505–517.

[147] S. Vijay-Kumar, C. E. Bugg, and W. J. Cook. Structure of ubiquitin refined at 1.8 Å resolution. Journal of Molecular Biology 194(1987):531–544.

[148] O. Vitek, C. Bailey-Kellogg, B. Craig, P. Kuliniewicz, and J. Vitek. Reconsidering complete search algorithms for protein backbone NMR assignment. Bioinformatics 21;Suppl 2(2005):ii230–ii236.

[149] O. Vitek, J. Vitek, B. Craig, and C. Bailey-Kellogg. Model-based assignment and inference of protein backbone Nuclear Magnetic Resonances. Statistical Applications in Genetics and Molecular Biology 3;1(2004).

[150] C. E. Wang, T. Lozano-Pérez, and B. Tidor. AMBIPACK: A systematic algorithm for packing of macromolecular structures with ambiguous distance constraints. Proteins: Structure, Function, and Genetics 32(1998):26–42.

[151] L. Wang and B. R. Donald. Analysis of a systematic search-based algorithm for determining protein backbone structure from a minimal number of residual dipolar couplings, in Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB), pp. 319–330, Stanford, CA, August 2004. PMID: 16448025.

[152] L. Wang and B. R. Donald. Exact solutions for internuclear vectors and backbone dihedral angles from NH residual dipolar couplings in two media, and their application in a systematic search algorithm for determining protein backbone structure. Journal of Biomolecular NMR 29;3(2004):223–242.

[153] L. Wang and B. R. Donald. An efficient and accurate algorithm for assigning nuclear Overhauser effect restraints using a rotamer library ensemble and residual dipolar couplings, in Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB), pp. 189–202, Stanford, CA, August 2005. PMID: 16447976.

[154] L. Wang and B. R. Donald. A data-driven, systematic search algorithm for structure determination of denatured or disordered proteins, in Proceedings of the LSS Computational Systems Bioinformatics Conference (CSB), pp. 68–78, Stanford, CA, August 2006. PMID: 17369626.

[155] L. Wang, R. Mettu, and B. R. Donald. An algebraic geometry approach to protein backbone structure determination from NMR data, in Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB), pp. 235–246, Stanford, CA, August 2005. PMID: 16447981.

[156] L. Wang, R. Mettu, and B. R. Donald. A polynomial-time algorithm for de novo protein backbone structure determination from NMR data. Journal of Computational Biology 13;7(2006):1276–1288.

[157] Y. X. Wang, J. Jacob, F. Cordier, P. Wingfield, S. J. Stahl, S. Lee-Huang, et al. Measurement of 3hJNC’ connectivities across hydrogen bonds in a 30 kDa protein. Journal of Biomolecular NMR 14;2(1999):181–184.

[158] Y. X. Wang, J. L. Marquardt, P. Wingfield, S. J. Stahl, S. Lee-Huang, D. Torchia, and A. Bax. Simultaneous measurement of 1H^1\text{H} - 15N^{15}\text{N} , 1H^1\text{H} - 13C′^{13}\text{C}' , and 15N^{15}\text{N} - 13C′^{13}\text{C}' dipolar couplings in a perdeuterated 30 kda protein dissolved in a dilute liquid crystalline phase. Journal of the American Chemical Society 120;29(1998):7385–7386.

[159] W. J. Wedemeyer, C. A. Rohl, and H. A. Scheraga. Exact solutions for chemical bond orientations from residual dipolar couplings. Journal of Biomolecular NMR 22(2002):137–151.

[160] H. Weidong and L. Wang. Residual dipolar couplings: Measurements and applications to biomolecular studies. Annual Reports on NMR Spectroscopy 58(2006):231–303.

[161] S. Wells, S. Menor, B. Hespenheide, and M. F. Thorpe. Constrained geometric simulation of diffusive motion in proteins. Physical Biology 2;4(2005):127–136.

[162] Wikipedia. NP-completeness. Wikipedia, the Free Encyclopedia, September 2008. Available at http://en.wikipedia.org/wiki/NP-complete.

[163] D. S. Wishart and B. D. Sykes. The 13C^{13}\text{C} chemical shift index: A simple method for the identification of protein secondary structure using 13C^{13}\text{C} chemical shift data. Journal of Biomolecular NMR 4(1994):171–180.

[164] D. S. Wishart, B. D. Sykes, and F. M. Richards. Relationship between nuclear magnetic resonance chemical shift and protein secondary structure. Journal of Molecular Biology 222;2(1991):311–333.

[165] D. S. Wishart, B. D. Sykes, and F. M. Richards. The 13C^{13}\text{C} chemical shift index: A fast and simple method for the identification of protein secondary structure using 13C^{13}\text{C} chemical shift data. Biochemistry 31;6(1992):1647–1651.

[166] K. Wuthrich. Protein recognition by NMR. Nature Structural Biology 7;3(2000):188–189.

[167] W. Y. Choy, M. Tollinger, G. A. Mueller, and L. E. Kay. Direct structure refinement of high molecular weight proteins against residual dipolar couplings and carbonyl chemical shift changes upon alignment: An application to maltose binding protein. Journal of Biomolecular NMR 21;1(2001):31–40.

[168] X. Wang, S. Bansal, M. Jiang, and J. H. Prestegard. RDC-assisted modeling of symmetric protein homo-oligomers. Protein Science; 17;5(2008):899–907.

[169] X. P Xu and D. A. Case. Automated prediction of 15N^{15}\text{N} , 13C′^{13}\text{C}' alpha’, 13C′^{13}\text{C}' beta’ and 13C′^{13}\text{C}' chemical shifts in proteins using a density functional database. Journal of Biomolecular NMR 21(2001):321–333.

[170] Y. Xu, Y. Zheng, J. S. Fan, and D. Yang. A new strategy for structure determination of large proteins in solution without deuteration. Nature Methods 3;11(2006):931–937.

[171] A. Yan, C. Langmead, and B. R. Donald. A probability-based similarity measure for Saupe alignment tensors with applications to residual dipolar couplings in NMR structural biology. International Journal of Robotics Research 24;2–3(2005):165–182. (Special Issue on Robotics Techniques Applied to Computational Biology.)

[172] J. Zamoon, A. Mascioni, D. D. Thomas, and G. Veglia. NMR solution structure and topological orientation of monomeric phospholamban in dodecylphosphocholine micelles. Biophysical Journal 85;4(2003):2589–2598.

[173] M. I. Zavodszky, M. Lei, M. F. Thorpe, A. R. Day and L. A. Kuhn. Modeling correlated main-chain motions in proteins for flexible molecular recognition. Proteins 57;2(2004):243–261.

[174] J. Zeng, C. Tripathy, P. Zhou, and B. R. Donald. A Hausdorff-based NOE assignment algorithm using protein backbone determined from residual dipolar couplings and rotamer patterns, in Proceedings of the LSS Computational Systems Bioinformatics Conference (CSB), pp. 169–181, Stanford, CA, August 2008. PMID. 19122773.

[175] M. Zweckstetter. Determination of molecular alignment tensors without backbone resonance assignment: Aid to rapid analysis of protein-protein interactions. Journal of Biomolecular NMR 27;1(2003):41–56.

[176] M. Zweckstetter and A. Bax. Single-step determination of protein substructures using dipolar couplings: Aid to structural genomics. Journal of the American Chemical Society 123;38(2001):9490–9491.

[177] J. Zeng, J. Boyles, C. Tripathy, L. Wang, A. Yan, P. Zhou, B. R. Donald. High-resolution protein structure determination starting with a global fold calculated from exact solutions to the RDC equations. Journal of Biomolecular NMR 45;3(2009):265–81.