Chapter 14Nuclear Vector Replacement

This lecture presents the nuclear vector replacement (NVR) algorithm, and its applications in automated NMR resonance assignments [1, 2] and three-dimensional (3D) structural homology detection [3, 4]. The expectation-maximization approach is introduced, which complements bipartite matching as a useful framework for many structural problems.

NVR stands for “Nuclear Vector Replacement.” It is named by analogy to “molecular replacement” in X-ray crystallography (chapters 47 and 48).

Experimental Input

NVR is an algorithm for computing resonance assignments given a putative 3D structural model of the target protein. This model is typically a PDB format structure. The following data are processed in the NVR algorithm: unassigned chemical shifts in HN−15NH^N-^{15}N HSQC spectra, HN−15NH^N-^{15}N RDCs in two media, amide exchange data, and unassigned peaks in 3D 15N^{15}N -NOESY spectra. The amide exchange information provides probabilistic classifications for the peaks in the HSQC corresponding to non-hydrogen-bonded, solvent-accessible backbone amide protons. All the HN−15NH^N-^{15}N RDC, H-D exchange and 15N^{15}N -NOESY data serve as the geometric constraints on assignment. Table 14.1 shows the information content and roles of the input data.

Nuclear Vector Replacement

The NVR algorithm consists of three phases: tensor estimation, resonance assignment, and structure refinement, as shown in figure 14.1. In the first phase, NVR estimates the alignment tensors in both media. In the second phase, NVR applies the estimated tensors, and uses an iterative computational process, such as a Bayesian or expectation/maximization framework, to search the optimal resonance assignments. After resonance assignments, the assigned RDCs are used to refine the structure of the model by using the algorithm in Wang and Donald [6]. In the following subsections, we will present more details on the tensor estimation and resonance assignment phases.

Table 14.1 Information contents and roles of the input data [1]

Experiment/Data Information Content Role
HN−15NH^{N-15}N HSQC HN,15NH^{N, 15}N chemical shifts Backbone resonances, cross-referencing NOESY
HN−15NH^{N-15}N RDC (in 2 media) Restraints on amide bond vector orientation Tensor determination, resonance assignment,
H-D exchange HSQC Identifies solvent exposed amide protons Tensor determination
HN−15NH^{N-15}N HSQC-NOESY Distance restraints between spin systems Tensor determination, resonance assignment
15N^{15}N TOCSY
Backbone structure
Chemical shift predictions
Side-chain chemical shifts
Tertiary structure
Restraints on assignment
Tensor determination, resonance assignment
Tensor determination, resonance assignment
Tensor determination, resonance assignment

Reprinted from [1]. Copyright 2004 IEEE.

Figure 14.1 Nuclear vector replacement [2].

Tensor Estimation

An alignment tensor SS is a symmetric and traceless 3×33 \times 3 matrix with five degrees of freedom, for example, three Euler angles α\alpha , β\beta and γ\gamma , and the axial DaD_a and rhombic DrD_r components of an ellipsoid scaling the dipolar couplings. The alignment tensor can be diagonalized as follows:

S=VΣVTS = V \Sigma V^T where V∈SO(3)V \in SO(3) is a 3×33 \times 3 rotation matrix that defines the principle order frame, and Σ\Sigma is a 3×33 \times 3 diagonal and traceless matrix containing the eigenvalues of SS and encoding DaD_a and DrD_r .

SO(3)SO(3) denotes the special orthogonal group of real 3×33 \times 3 invertible matrices. It is the intersection of the orthogonal group O(3)O(3) of orthogonal matrices, and the special linear group SL(3)SL(3) of matrices with determinant +1+1 . SO(3)SO(3) is isomorphic to the group of three-dimensional rotations.

The diagonal elements of Σ\Sigma can be obtained based on the powder pattern method. Given Σ\Sigma , a rotation matrix V(α,β,γ)V(\alpha, \beta, \gamma) , corresponding to an alignment tensor SS , is found such that the Kullback-Leibler distance is minimized between the distribution of unassigned experimental RDCs and the distribution of the back-computed RDCs.

Time Complexity The eigenvalues of SS are computed in O(nk3)O(nk^3) time, where nn is the number of experimental RDCs and kk is the resolution of the search-grid over SO(3)SO(3) . The rotation matrix is calculated in O(nk3)O(nk^3) time. Given Σ\Sigma and VV , constructing SS takes only O(1)O(1) time. Thus, the total running time for tensor estimation is O(nk3)O(nk^3) . The Euler angle representation of three-dimensional rotations V∈SO(3)V \in SO(3) is familiar to many students; however, it suffers from singularities. A preferred representation of rotations is unit quaternions. Geometrically, quaternions may be represented by the three-dimensional sphere S3S^3 , which is a double cover of SO(3)SO(3) . That is, if q∈S3q \in S^3 is a quaternion, then we have a smooth map π:S3→SO(3)\pi : S^3 \rightarrow SO(3) such that π(q)\pi(q) is the rotation by qq and π(q)=π(−q)\pi(q) = \pi(-q) . The quaternions, like the Euler angles, form a three-dimensional space (S3S^3) and therefore can be searched using three parameters (similar to α,β,γ\alpha, \beta, \gamma) to construct a grid over S3S^3 . Only half of S3S^3 must be searched, since π(q)=π(−q)\pi(q) = \pi(-q) .

Resonance Assignment

Based on the estimated tensors S1S_1 and S2S_2 in two alignment media, the back-computed RDCs are obtained according to the following equation:

d=DmaxvTSiv,(i=1,2),(14.1)d = D_{\max} v^T S_i v, \quad (i = 1, 2), \qquad(14.1) where DmaxD_{\max} is the dipolar interaction constant, and vv is the internuclear vector orientation.

Let QQ be the set of HSQC peaks, RR be the set of residues, DmD_m be the set of experimental RDCs in the medium mm , and BmB_m be the back-computed RDCs in the medium mm , based on SmS_m . Let MmM_m be the assignment probability matrix for the medium mm such that

Mm(q,r)=Pr⁡(q↦r|Sm)=N(dm(q)−bm(r,Sm),μm,σm),(14.2)M_m(q, r) = \Pr(q \mapsto r | S_m) = N(d_m(q) - b_m(r, S_m), \mu_m, \sigma_m), \qquad(14.2) where q∈Qq \in Q , r∈Rr \in R , dm(q)∈Dmd_m(q) \in D_m , bm(r,Sm)∈Bmb_m(r, S_m) \in B_m , and N(dm(q)−bm(r,Sm),μm,σm)N(d_m(q) - b_m(r, S_m), \mu_m, \sigma_m) denotes the normal distribution function with the observed variable dm(q)−bm(r,Sm)d_m(q) - b_m(r, S_m) , the mean μm\mu_m , and the standard deviation σm\sigma_m . Each entry in MmM_m will be set to zero if the assignment q↦rq \mapsto r violates some geometric constraint, such as the dNNSd_{\text{NNS}} from 15N-NOESY^{15}\text{N-NOESY} spectra, or amide exchange. The dNNSd_{\text{NNS}} provide distance constraints between peaks that can be correlated to the residues in the model, while the H-D exchange information identifies fast-exchanging amide protons that are likely to be solvent-exposed and non-hydrogen-bonded, and can be correlated to the structure model.

Equation (14.2) is used to compute the assignment probability at each iteration. The most likely assignment in each medium is considered. Let r1(q),r2(q)∈Rr_1(q), r_2(q) \in R be the most likely assignments of peak qq in media 1 and 2. The assignment q↦rq \mapsto r is added into the master list of assignments if both following conditions are satisfied:

r1(q)=r2(q)r_1(q) = r_2(q) and

rm(q)≠rm(k),∀k∈Q,k≠q.r_m(q) \neq r_m(k), \quad \forall k \in Q, k \neq q.

It is possible that the second condition is not satisfied. In this case, a maximum bipartite matching is chosen.

Suppose that peak qq has been assigned to rr , then qq and rr are removed from the consideration of next iterations. At the end of each iteration, the alignment tensors S1S_1 and S2S_2 are refined based on the master list of assignments and model. At the same time, the assignment probabilities are renormalized and updated.

Time Complexity It takes O(n2)O(n^2) time to construct the probability matrices. Updating the alignment tensors S1S_1 and S2S_2 takes O(n2)O(n^2) time. Since at least one residue is assigned at each iteration, there are at most O(n)O(n) iterations. Thus, all assignments are guaranteed to be finished in O(n3)O(n^3) time. The time complexity has been improved to be O(n5/2log⁡(cn))O(n^{5/2} \log(cn)) in Langmead and Donald [5], where cc is the maximum edge-weight in an integer-weighted bipartite graph.

An Expectation/Maximization NVR Algorithm

Langmead and Donald [1] applied an expectation/maximization NVR algorithm for automated NMR resonance assignments. In the expectation/maximization framework, the observed variables include chemical shifts, dNNSd_{\text{NNS}} , amide exchange rates. The hidden variables include the correct resonance assignments and the correct alignment tensors. Let XX be the set of observed variables, and YY be the set of hidden variables. Let Θ\Theta denote the set of all assignments obtained so far. Initially, Θ\Theta is set to be empty, and then grows as the algorithm finds more assignments. The Expectation (E) step of the EM algorithm computes the following expectation:

E(Θ∪Θ′|Θ)=E(log⁡Pr⁡(X,Y|Θ∪Θ′)),E(\Theta \cup \Theta' | \Theta) = E(\log \Pr(X, Y | \Theta \cup \Theta')), where Θ′\Theta' denotes the set of new assignments that is disjoint with the previous set Θ\Theta . The Maximization (M) step computes the new assignment Θ*\Theta^* that has the maximum likelihood:

Θ*=argmax⁡Θ′E(Θ∪Θ′|Θ).\Theta^* = \operatorname{argmax}_{\Theta'} E(\Theta \cup \Theta' | \Theta).

At the same time, the algorithm updates the master list of assignment, that is, Θ←Θ∪Θ*\Theta \leftarrow \Theta \cup \Theta^* . Also, the alignment tensors are recomputed at the end of each iteration, based on updated assignments in Θ\Theta . The algorithm terminates when all peaks have been assigned.

3D Structural Homology Detection via NVR

Given unassigned RDCs of a target protein and a set of known models (protein structures in PDB format) in a database, we measure the 3D structural homology between the target protein and each known model by computing the likelihood of the assignment from the experimental RDCs to the model. We run the NVR algorithm for each model in the database, and then rank them by the likelihoods of the assignments.

Time Complexity Suppose that there are in total kk models in the database. Since the NVR algorithm runs in O(n5/2log⁡(cn))O(n^{5/2} \log(cn)) time, processing all kk proteins takes O(kn5/2log⁡(cn))O(kn^{5/2} \log(cn)) . Finally, sorting all kk models according to their likelihoods of assignments takes O(klog⁡k)O(k \log k) time. Thus, the total required time is O(kn5/2log⁡(cn)+klog⁡k)O(kn^{5/2} \log(cn) + k \log k) .

Matching Modulo a Group, and Clustering Modulo a Group

NVR for automated NMR resonance assignments can be viewed as a matching problem on a quotient space of (bond-vector) orientations, induced by a quadratic form ξ\xi on the 2-sphere S2S^2 . ξ\xi is given by the familiar RDC tensor equation (eq. 14.3):

d=ξ(v,v)=DmaxvTSv,(14.3)d = \xi(v, v) = D_{\max} v^T S v, \quad (14.3) from above. Using the alignment tensor SS , ξ\xi is parameterized by the Lie group SO(3)×ℝ2SO(3) \times \mathbb{R}^2 . SS is traceless and symmetric. When the eigenvalues of SS can be experimentally estimated (as is often the case), the degrees of freedom reduce to SO(3)SO(3) . Hence, 3D structural homology detection from unassigned NMR data (enabling rapid fold determination) can be performed by combinatorial optimization, searching over SO(3)SO(3) to minimize a functional that compares distributions generated by ξ\xi ’s image of the bond vectors from putative database protein models (chapter 13). These algorithms are developed further in chapters 15–18.

Using the techniques in chapters 4, 13, and 15–18, the RDC equations can be combined with protein kinematics to reduce the problem of protein structure determination from RDCs, to a search over the (discrete and finite number of) roots of low-degree univariate polynomial equations. These techniques have been developed for NH RDCs in two media, and for NH and CH (i.e., CαC^\alpha -H α^\alpha) RDCs in one medium. They can be extended to use alternative RDCs (on different bond vectors), additional RDCs, or additional aligning media.

In some cases, such as NH RDCs in two media, or NH and CH RDCs in one medium, solving the resulting polynomial equations (generically) results in multiple (albeit finite and discrete) roots. Hence, the structure determination algorithm must typically perform a discrete and combinatorial search for the correct root, i.e., the true solution.

In 3D structural homology detection, there are two ambiguities in matching: which bond vector, and which root. The following toy example illustrates the concept. We consider the case of NH

RDCs in two media. Suppose we have NH bond vectors in a putative structural model from only two residues, Arg25 and Phe53. Call these v1v_1 and v2v_2 , and without loss of generality consider them to be unit vectors lying on S2S^2 . Now, suppose from the NMR data there are two unassigned residues A and B, from which we compute roots w1,…,w4w_1, \dots, w_4 and u1,…,u4u_1, \dots, u_4 to the RDC equations. These roots define possible NH bond vectors for the two unassigned residues A and B. Thus, we will think of the NH bond vector of residue A as lying in the set W={w1,…,w4}W = \{w_1, \dots, w_4\} . The NH bond vector of residue B lies in the set U={u1,…,u4}U = \{u_1, \dots, u_4\} . Note that UU and WW each have four points (in this example) and therefore are discrete and finite subsets of S2S^2 . A legal matching has the form ((v1,wi),(v2,uj))((v_1, w_i), (v_2, u_j)) or ((v1,ui),(v2,wj))((v_1, u_i), (v_2, w_j)) , for i,j∈{1,…,4}i, j \in \{1, \dots, 4\} . But all matches of the form ((v1,wi),(v2,uj))((v_1, w_i), (v_2, u_j)) and ((v1,ui),(v2,wj))((v_1, u_i), (v_2, w_j)) are illegal since in the first case wiw_i and wjw_j are roots of the same polynomial, and hence correspond to two possible but mutually exclusive choices for same bond vector based on the data. Similarly, uiu_i and uju_j are both roots of a (different) polynomial, and correspond to mutually exclusive choices for a single bond vector in the data. If UU and WW are viewed as sets, then the legal matchings have a simple “XOR” (exclusive OR) structure. However, UU and WW have a group structure, since each is constructed from the roots of a polynomial. The group-theoretic viewpoint gives the problem a fascinating mathematical structure, that can likely be exploited by advanced algorithms. We call this problem matching modulo a group. It is worth explaining the terminology. If GG is the group of UU , then the intuition is, to say “ uiu_i is the same as uju_j modulo GG ” signalizes that “ uiu_i and uju_j are the same except for differences accounted for or explained by GG .” The word modulo is mathematical shorthand to denote equivalence in the orbit space S2/GS^2/G . S2/GS^2/G is the quotient of the group action GG on the manifold S2S^2 .

To summarize, in NVR, bond vector orientations from a putative structural model can be matched against the multiple roots of the RDC equations. Only one root-match per model bond vector can be correct. This problem may be viewed as matching modulo a group, where the group encodes the multiplicity of the roots, and is related to the Galois group of the RDC-kinematic polynomials derived by Wang and Donald (chapters 16, 17). While the problems of matching and clustering have received a great deal of attention in computer science, machine vision, and computational biology, the problems of matching modulo a group and clustering modulo a group are relatively new, and are of considerable biological and computational importance. Clustering modulo a group will be discussed later, in chapter 47.

References

  • [1] C. J. 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.
  • [2] C. J. Langmead, A. K. Yan, R. H. Lilien, L. Wang, and B. R. Donald. A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments. RECOMB (2003): 176–187. Journal Computational Biology 11;2–3(2004):277–298.
  • [3] C. J. Langmead and B. R. Donald. 3D structural homology detection via unassigned residual dipolar couplings. Proceedings of IEEE Computational Systems Bioinformatics Conference (CSB), Stanford University, Palo Alto (August 10, 2003), pp. 209–217.

  • [4] C. J. Langmead and B. R. Donald. High-throughput 3D structural homology detection via NMR resonance assignment. Proceedings of IEEE Computational Systems Bioinformatics Conference (CSB), Stanford, (August, 2004), pp. 278–289.
  • [5] C. J. Langmead and B. R. Donald. An improved nuclear vector replacement algorithm for nuclear magnetic resonance assignment. Tech. Rep. TR2004-494, Dartmouth Department of Computer Science, 2004.
  • [6] 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.