Chapter 4MBM, SVD, PCA, and RDCs

In this chapter, we review the basic ideas of maximum bipartite matching (MBM), singular value decomposition (SVD), principal component analysis (PCA), and residual dipolar coupling (RDC) geometry. These algorithms are useful in computational biology in general, and structural biology and molecular biophysics in particular, and will be used in several applications in this book.

Each of these topics could be covered in some depth and breadth, even requiring several lectures. It is useful to have the basic primer on these techniques in one short chapter here. Later, we will explore details and applications of these fundamental concepts.

MBM

The input of an MBM problem is a complete bipartite graph G=(V,E)G = (V, E) with a weight function w:E→ℝ+w : E \rightarrow \mathbb{R}^+ , such that V=L∪RV = L \cup R , L∩R=∅L \cap R = \emptyset , and E=R×L∪L×RE = R \times L \cup L \times R . More generally, E⊆R×L∪L×RE \subseteq R \times L \cup L \times R , but we can add edges with weight 0 to the graph to make it complete bipartite. Here, LL can be visualized as the set of vertices on the left, and RR as the set of vertices on the right.

A matching is a set of nonintersecting edges. The output of MBM is a matching EmE_m between LL and RR with the highest weight. That is,

Em=argmax⁡E′⊆E,s.t.∀e1,e2∈E′,e1∩e2=∅∑e∈E′w(e).E_m = \operatorname{argmax}_{E' \subseteq E, s.t. \forall e_1, e_2 \in E', e_1 \cap e_2 = \emptyset} \sum_{e \in E'} w(e).

Example 4.1 In the assignment problem, we want to match the residues in the model with the peaks observed in HSQC. This problem is modeled as an MBM problem as follows:

  1. Let L={All the residues in the model}L = \{\text{All the residues in the model}\} , R={Peaks in HSQC}R = \{\text{Peaks in HSQC}\} .
  2. For any i∈Li \in L , j∈Rj \in R , let

w(i,j)=|Di−vjSvj′|.w(i, j) = |D_i - v_j S v'_j|.

Here DjD_j is the actual RDC data obtained from experiments, and vjSvj′v_j S v'_j is the simulated RDC data back-calculated from the model.

The Hopcroft–Karp algorithm finds the maximum bipartite matching in O(|V||E|)O(\sqrt{|V|}|E|) time [1, 2].

An MBM problem can be very sensitive to noise, as shown in the following example.

Example 4.2 Let L={l1,l2}L = \{l_1, l_2\} , R={r1,r2}R = \{r_1, r_2\} , the ground truth weight is w(l1,r1)=10w(l_1, r_1) = 10 , w(l2,r2)=10w(l_2, r_2) = 10 , w(l1,r2)=10w(l_1, r_2) = 10 , w(l2,r1)=9.9w(l_2, r_1) = 9.9 . Then, the maximum matching is Em={(l1,r1),(l2,r2)}E_m = \{(l_1, r_1), (l_2, r_2)\} . However, if there is a noise on the weight of the edge (l1,r2)(l_1, r_2) such that the weight we observed is 11, then the maximum matching will become {(l1,r2),(l2,r1)}\{(l_1, r_2), (l_2, r_1)\} , which does not share any edge with the ground truth.

SVD

Definition

SVD is a technique to decompose a matrix into the product of three matrices. For any mm -by- nn matrix XX , there exists a decomposition of XX to the product of three matrices X=USVTX = USV^T such that

  1. UU is an m×mm \times m unitary matrix, that is, M×MT=ImM \times M^T = I_m where ImI_m is the identity matrix.
  2. SS is a diagonal matrix, which means that all the entries outside the main diagonal of SS are zero. Thus, S=diag(s1,…,sk,0,…,0)S = \text{diag}(s_1, \dots, s_k, 0, \dots, 0) , s1,…,sk>0s_1, \dots, s_k > 0 , k=rank(S)=rank(X)k = \text{rank}(S) = \text{rank}(X) .
  3. VTV^T is the transpose of a unitary nn -by- nn matrix VV .

Properties

One of the most important properties of SVD is that it can be used to calculate the best solution to a linear system A𝒙=𝒃A\mathbf{x} = \mathbf{b} that minimizes the least-square norm. The problem is defined as follows:

Problem 4.1 Let AA be an m×nm \times n matrix, and 𝒃\mathbf{b} be an m×1m \times 1 vector. Find an n×1n \times 1 vector 𝒙̂\hat{\mathbf{x}} that minimizes ∥A𝒙−𝒃∥\|A\mathbf{x} - \mathbf{b}\| , where ∥A𝒙−𝒃∥=∑i=1m((A𝒙)i−𝒃i)2\|A\mathbf{x} - \mathbf{b}\| = \sqrt{\sum_{i=1}^m ((A\mathbf{x})_i - \mathbf{b}_i)^2} , (A𝒙)i(A\mathbf{x})_i is the ii th component of A𝒙A\mathbf{x} , etc. That is

𝒙̂=arg⁡min𝒙∥A𝒙−𝒃∥.\hat{\mathbf{x}} = \arg \min_{\mathbf{x}} \|A\mathbf{x} - \mathbf{b}\|.

𝒙̂\hat{\mathbf{x}} can be calculated as follows by applying SVD to AA .

  • Calculate the SVD of AA . Let A=USVTA = USV^T , where S=diag(s1,…,sk,0,…,0)S = \text{diag}(s_1, \dots, s_k, 0, \dots, 0) . Let S†=diag(1s1,…,1sr,0,…,0)S^\dagger = \text{diag}(\frac{1}{s_1}, \dots, \frac{1}{s_r}, 0, \dots, 0) be an n×mn \times m diagonal matrix.
  • Let A†=VS†UTA^\dagger = VS^\dagger U^T be the pseudoinverse of AA .
  • Let 𝒙̂=A†𝒃\hat{\mathbf{x}} = A^\dagger \mathbf{b} .

It can be proved that 𝒙̂\hat{\mathbf{x}} is the minimal-norm least-square solution to A𝒙=𝒃A\mathbf{x} = \mathbf{b} .

When AA is symmetric (A=ATA = A^T), and positive semidefinite (that is, for any vector 𝒙\mathbf{x} , 𝒙TA𝒙≥0\mathbf{x}^T A \mathbf{x} \geq 0), then U=VU = V and the s1,…,srs_1, \dots, s_r are the eigenvalues of AA .

PCA

PCA is a technique to reduce the dimension of high-dimensional data, in order to simplify the analysis. PCA is an orthogonal linear transformation that transforms the data set to another coordinate system such that the distance variance among data is mainly in the first several dimensions. PCA is useful because in many real-life instances, we do not know the structure of the problem, so we have to model the data in a very high-dimensional space. However, the data set itself has some underlying structure such that the variance of data can be approximately characterized in a space of much lower dimension. For example, imagine a case where, in ℝ100\mathbb{R}^{100} , all of the data are generated approximately in a line (1-dimensional space). Then PCA can find a new coordinate system such that this line is the first coordinate (also known as the first principal component). To analyze the distance between points in the data set, we do not need to consider the remaining 99 dimensions.

Calculating PCA by SVD

Let X=(p1,…,pn)X = (p_1, \dots, p_n) be an m×nm \times n matrix, in which each column pip_i is a data vector in ℝm\mathbb{R}^m . Without loss of generality, we assume that XX has zero empirical mean, that is, ∑i=1npi=0\sum_{i=1}^n p_i = 0 .

To find the subspace that best represents the variance of XX , let C=XXTC = XX^T be the covariance. Then, compute the SVD for CC . Notice that CC is symmetric and positive semidefinite, so the SVD of CC must be C=VSVTC = VSV^T , where the diagonal of SS consists of all the eigenvalues of CC , and the column vectors of VV are the normalized eigenvectors (recall that viv_i is the normalized eigenvector of an eigenvalue λi\lambda_i of CC , if ∥vi∥=1\|v_i\| = 1 and Cvi=λiviCv_i = \lambda_i v_i). Then, we choose the largest eigenvalue eigenvectors as the axes to project XX on. Without loss of generality, suppose λ1,…,λk\lambda_1, \dots, \lambda_k are the kk largest eigenvalues of CC , and let v1,…,vkv_1, \dots, v_k be their eigenvectors, respectively. Then, V′=(v1T,…,vkT)V' = (v_1^T, \dots, v_k^T) is the transformation matrix, and V′XV'X is the projection of the original data vector XX to a kk -dimensional subspace that best represents the variance of the data in XX .

RDCs

NOEs provides interproton distance information for a protein. However, such information is only available when the distance between two nuclei is short (under 6 Å). RDCs, on the other hand, can provide global structural information between spins even when the distance between them is very large.

Definition 4.1 The residual dipolar coupling between two spins aa and bb , is defined as follows:

DIS=D=μ0γaγbℏ4π2⟨ra,b3⟩⟨3cos⁡2θ−12⟩,(4.1)D_{IS} = D = \frac{\mu_0 \gamma_a \gamma_b \hbar}{4\pi^2 \langle r_{a,b}^3 \rangle} \left\langle \frac{3 \cos^2 \theta - 1}{2} \right\rangle, \quad (4.1) where ℏ\hbar is the Planck’s constant, γ\gamma is the gyromagnetic ratio, ra,br_{a,b} is the interspin distance, θ\theta is the angle between the interspin vector and the external magnetic field 𝑩\mathbf{B} (see figure 3.5). In NMR, spins aa and bb are sometimes called II and SS (see figure 4.1).

Figure 4.1For example, in NVR, RDC is used to measure the orientation of the NH bond vector for each residue (chapter 14). Therefore, the distance rr in (eq. 4.1) is known. In this case the RDC measures the global orientation of the NH bond.

Exercise How can SVD be used to analyze RDC data? What is the relationship between this use of SVD, and the PCA method?

References

  • [1] John E. Hopcroft and Richard M. Karp. An n5/2n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal of Computing 2(4) (1973): 225–231.
  • [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, pp. 696–697.