Chapter 36SemiDefinite Programming and Distance Geometry with Orientation Constraints

This chapter introduces Semidefinite programming and its applications in two areas: the side-chain positioning problem and the sensor network localization problem. We present the problem of distance geometry with orientation constraints: we first introduce the graph embedding problem with angle information, and then revisit the problem of protein backbone determination using the global orientational constraints from RDC data.

SemiDefinite Programming and Two Applications

Overview of SemiDefinite Programming

Semidefinite programming (SDP) has been one of the most exciting developments in mathematical programming since the 1990s [4]. Semidefinite programming is a special case of convex programming, in which we must optimize a linear function of symmetric matrices subject to linear equality constraints, and where the matrix must be positive semidefinite.1 For any additive error ε>0\varepsilon > 0 , semidefinite programs can be solved in polynomial time, in terms of both the size of input and log⁡(1/ε)\log(1/\varepsilon) , using the ellipsoid algorithm or interior-point method.

Application in the Side-Chain Positioning Problem

In the side-chain positioning problem (See chapters 11–12), we are given a backbone of length pp , and a set of side-chains {ir}\{i_r\} , also called rotamers, for each residue position ii , and our objective is to find a sequence of side-chains that minimizes the following energy function:

ℰ=E0+∑iE(ir)+∑i<jE(ir,js),\mathcal{E} = E_0 + \sum_i E(i_r) + \sum_{i < j} E(i_r, j_s), where E0E_0 denotes the self-energy of the backbone, E(ir)E(i_r) denotes the energy resulting from the interaction between the backbone and the rotamer iri_r at position ii , and E(ir,js)E(i_r, j_s) denotes the energy resulting from the interaction between chosen rotamers iri_r and jsj_s .

1 Suppose that XX is an n×nn \times n matrix. Then XX is a positive semidefinite (PSD) matrix if vTXv≥0v^T X v \geq 0 for any v∈ℝnv \in \mathbb{R}^n .

The side-chain positioning problem can also be formulated in graph-theoretic terms. Let GG denote a pp -partite graph with node set V=V1∪…∪VpV = V_1 \cup \dots \cup V_p , where ViV_i represents the set of rotamers {ir}\{i_r\} at position ii . Each node u∈Viu \in V_i is associated with a weight Euu=E(ir)E_{uu} = E(i_r) . Each edge between nodes u∈Viu \in V_i (corresponding to iri_r) and v∈Vjv \in V_j (corresponding to jsj_s) (i≠ji \neq j) is assigned a weight Euv=E(ir,js)E_{uv} = E(i_r, j_s) . Now, the side-chain positioning problem is converted into the problem of finding a node per ViV_i to minimize the weight sum of the induced subgraph.

The side-chain positioning problem has been proven to be NP-hard [5] and even hard to approximate [3]. It can be directly formulated into the following integer quadratic programming problem:

minimize∑(u,v)∈GEuvxuxv(36.1)\text{minimize} \quad \sum_{(u,v) \in G} E_{uv} x_u x_v \quad (36.1)

subject to∑u∈Vixu=1 for i=1,…,p.\text{subject to} \quad \sum_{u \in V_i} x_u = 1 \text{ for } i = 1, \dots, p.

xu∈{0,1}.x_u \in \{0, 1\}.

We next show how to relax this integer quadratic programming problem to a semidefinite programming formulation [3]. First, we add a new singleton vertex set, V0={u0}V_0 = \{u_0\} , into graph GG . The formulation in (36.1) can be converted into the following, equivalent program:

minimize∑(u,v)∈GEuvxuxv(36.2)\text{minimize} \quad \sum_{(u,v) \in G} E_{uv} x_u x_v \quad (36.2)

subject to∑u,v∈Vixuxv=1 for i=0,1,…,p.\text{subject to} \quad \sum_{u,v \in V_i} x_u x_v = 1 \text{ for } i = 0, 1, \dots, p.

∑u∈Vixu0xu=1 for i=0,1,…,p\sum_{u \in V_i} x_{u_0} x_u = 1 \text{ for } i = 0, 1, \dots, p

xuxu=xu0xux_u x_u = x_{u_0} x_u

xu∈{0,1} for all u.x_u \in \{0, 1\} \text{ for all } u.

We relax the requirement xu∈{0,1}x_u \in \{0, 1\} to 0≤xuTxv≤10 \leq x_u^T x_v \leq 1 for all uu and vv , and then obtain the following semidefinite programming formulation:

minimize∑(u,v)∈GEuvxuxv(36.3)\text{minimize} \quad \sum_{(u,v) \in G} E_{uv} x_u x_v \quad (36.3)

subject toxuu=xu0u and xuv≥0\text{subject to} \quad x_{uu} = x_{u_0u} \text{ and } x_{uv} \geq 0

∑u∈Vixu0u=∑u,v∈Vixu,v=1 for i=0,1,…,p.\sum_{u \in V_i} x_{u_0u} = \sum_{u,v \in V_i} x_{u,v} = 1 \text{ for } i = 0, 1, \dots, p.

We can obtain a solution of the preceding SDP system within any desired level of accuracy ε\varepsilon in polynomial time by using the ellipsoid algorithm or interior-point method. After that, we use a randomized rounding scheme to round each vector 0≤xu≤10 \leq x_u \leq 1 to 0 or 1. The basic idea is to sample each position from a specified probability distribution in which long vectors have a higher probability of being selected. For more details of the rounding scheme, see section 3 in Biswas et al. [2].

Application in the Sensor Network Localization Problem

It is interesting that SDP can also be used to solve the other problems, such as those in sensor networks. We give one example now.

In a sensor network in ℝ2\mathbb{R}^2 , we are given nn sensors and mm anchors. An anchor is a node whose position aka_k , k=1,…,mk = 1, \dots, m , in ℝ2\mathbb{R}^2 is known. We also know NxN_x , a set of Euclidean distances dijd_{ij} between two sensors xix_i and xjx_j , and NaN_a , a set of Euclidean distances djkd_{jk} between a sensor xjx_j and an anchor aka_k . The sensor network localization problem is to find all xjx_j , j=1,2,…,nj = 1, 2, \dots, n , that satisfy all the distance constraints

∥xj−xi∥2=dji2,∀(j,i)∈Nx\|x_j - x_i\|^2 = d_{ji}^2, \forall (j, i) \in N_x

∥xj−ak∥2=djk2,∀(j,k)∈Na.\|x_j - a_k\|^2 = d_{jk}^2, \forall (j, k) \in N_a.

Let X=(x1,x2,…,xn)X = (x_1, x_2, \dots, x_n) . Then the sensor network localization problem can be formulated into the following matrix form:

find X∈ℝ2×n,Y∈ℝn×n(36.4)\text{find } X \in \mathbb{R}^{2 \times n}, Y \in \mathbb{R}^{n \times n} \qquad(36.4)

subject to (ei−ej)TY(ei−ej)=dji2,∀(j,i)∈Nx\text{subject to } (e_i - e_j)^T Y (e_i - e_j) = d_{ji}^2, \forall (j, i) \in N_x

(ak−ej)T(I2XXTY)(ak−ej)=djk2,∀(j,k)∈Na.\begin{pmatrix} a_k \\ -e_j \end{pmatrix}^T \begin{pmatrix} I_2 & X \\ X^T & Y \end{pmatrix} \begin{pmatrix} a_k \\ -e_j \end{pmatrix} = d_{jk}^2, \forall (j, k) \in N_a.

Y=XTX.Y = X^T X.

This form can be relaxed to a semidefinite program by changing constraint Y=XTXY = X^T X to Y≽XTXY \succeq X^T X . Here, the symbol ≽\succeq means positive, semidefinite:

find Z∈ℝ(n+2)×(n+2)(36.5)\text{find } Z \in \mathbb{R}^{(n+2) \times (n+2)} \qquad(36.5)

subject to (1,0,0)TZ(1,0,0)=1\text{subject to } (1, 0, 0)^T Z (1, 0, 0) = 1

(0,1,0)TZ(0,1,0)=1(0, 1, 0)^T Z (0, 1, 0) = 1

(1,1,0)TZ(1,1,0)=2(1, 1, 0)^T Z (1, 1, 0) = 2

(0,ei−ej)TZ(0,ei−ej)=dji2,∀(j,i)∈Nx(0, e_i - e_j)^T Z (0, e_i - e_j) = d_{ji}^2, \forall (j, i) \in N_x

(ak,−ej)TZ(ak,−ej)=dji2,∀(j,i)∈Na(a_k, -e_j)^T Z (a_k, -e_j) = d_{ji}^2, \forall (j, i) \in N_a

Z=(I2XXTY)≽0.Z = \begin{pmatrix} I_2 & X \\ X^T & Y \end{pmatrix} \succeq 0.

The ε\varepsilon -solution of this SDP system—that is, the solution within ε\varepsilon error distance from the optimal one—can be computed in time O(n+k(n3+n2k+k3)log⁡1ε)O(\sqrt{n+k}(n^3+n^2k+k^3) \log \frac{1}{\varepsilon}) using the interior-point algorithm, where k=3+|Nx|+|Na|k = 3 + |N_x| + |N_a| .

Distance Geometry with Orientation Constraints

We now discuss the graph embedding problem with local angle information, and then compare with the protein structure determination problem based on global RDC orientational constraints.

Graph Embedding with Angle Information

In lskl_s^k space, the distance between two points (x1,…,xk)(x_1, \dots, x_k) and (y1,…,yk)(y_1, \dots, y_k) in kk -dimensional space is measured according to the lsl_s norm, that is,

∥(x1,…,xk)−(y1,…,yk)∥=(x1−y1)s+…+(xk−yk)ss.\|(x_1, \dots, x_k) - (y_1, \dots, y_k)\| = \sqrt[s]{(x_1 - y_1)^s + \dots + (x_k - y_k)^s}.

In a graph embedding problem, we are given a graph G=(P,E)G = (P, E) , and lengths D(p,q)D(p, q) for all edges {p,q}∈E\{p, q\} \in E . Our objective is to embed GG into a lskl_s^k space by a map f:P→lskf: P \rightarrow l_s^k such that the following graph distortion is minimized:

max(p,q)∈E∥f(p)−f(q)∥s/D(p,q).\max_{(p,q) \in E} \|f(p) - f(q)\|_s / D(p, q).

Badoiu et al. [1] considered the embedding problem assuming multiplicative errors on edges and additive errors on angles. The naïve setup of the problem is nonconvex and difficult to solve. The following shows how to relax the problem to a convex problem at the cost of some error ε\varepsilon [1].

Consider a distance geometry problem with orientational restraints, where the angle of an edge (p,q)(p, q) with the xx -axis is given up to angular error γ\gamma . As shown in figure 36.1, the distance and angle information for the edge (p,q)(p, q) specifies a nonconvex feasible region for qq , given a fixed point pp . We can add an edge (a,b)(a, b) and relax the feasible region to be convex. Next, a linear program can be used to solve the problem in polynomial time. The maximum expansion error is, at most, (1+ε)/cos⁡γ(1 + \varepsilon)/\cos \gamma after computing the maximum distance in the cutoff region.

Exercise 36.1 Compare the approximation algorithm above to the lower bounds in chapter 32 and [6], which prove there is an obstruction to obtaining an approximation for graph embedding without orientational constraints. How does the addition of this orientation information enable a provably good, polynomial-time approximation algorithm? In protein structure determination, how could such information be measured experimentally?

Figure 36.1 The relaxation in the embedding problem. Feasible region of a point qq with respect to pp given the ℓ2\ell_2 distance within a multiplicative error ε\varepsilon and given the angle to the xx axis within an additive angular error γ\gamma [1].

Protein Structure Determination from RDCs

We close with an open problem. Let us review RDC-based protein structure determination (chapters 15–18). Given a bond vector vv , its corresponding RDC rr can be measured by

r=DmaxvTSv,r = D_{\max} v^T S v, where DmaxD_{\max} is a physical constant, and SS is the alignment tensor.

Let (x,y,z)(x, y, z) be the coordinates of bond vector vv . We have

r=Sxxx2+Syyy2+Szzz2,r = S_{xx}x^2 + S_{yy}y^2 + S_{zz}z^2, where SxxS_{xx} , SyyS_{yy} , and SzzS_{zz} are the three diagonal elements of SS in the principal order frame.

Suppose we are given RDCs for a bond vector vv in two independent media, then we have the following relations:

r=Sxxx2+Syyy2+Szzz2,r = S_{xx}x^2 + S_{yy}y^2 + S_{zz}z^2,

r′=Sxx′x′2+Syy′y′2+Szz′z′2,r' = S'_{xx}x'^2 + S'_{yy}y'^2 + S'_{zz}z'^2,

(x′y′z′)=R12(xyz),\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} = R_{12} \begin{pmatrix} x \\ y \\ z \end{pmatrix}, where the third equation stands for the transformation relationship (a rigid rotation) between the two alignment tensors. This system is solvable, and by symmetry, there are up to 8 possible solutions (see chapters 15–18).

Figure 36.2 The computation of alignment tensors.

Suppose we are given N-H RDCs in two media for a peptide chain. We can compute all possible N-H bond vectors according to the preceding equations. If we can fix the position of the first peptide plane, there are two possible (ϕ,ψ)(\phi, \psi) angles for each pair of bond vectors in two adjacent peptide planes, based on trigonometry and inverse kinematics computation. Thus, we have a discrete and finite set of all possible conformations for this peptide chain. However, two issues still remain to be addressed: First, how do we fix the first peptide plane, and second how do we compute the alignment tensors S1S_1 and S2S_2 . In [7], an ideal helix model is initially used to represent a helix in the protein structure, as shown in figure 36.2. Then an initial alignment tensor is calculated using SVD to fit ri≈DmaxviTSvir_i \approx D_{\max} v_i^T S v_i , that is, minimize ∑|ri−DmaxviTSvi|\sum |r_i - D_{\max} v_i^T S v_i| . Based on the computed alignment tensor, a DFS-based method is used to search for the structure, based on which we can recompute the alignment tensor. The orientation of the first peptide plane can be obtained based on the computed alignment tensor and two known bond vectors, N-C α^\alpha and N-H in the plane.

A divide-and-conquer strategy is used to determine the overall protein structure. We first divide the whole protein into several fragments (according to secondary structure elements). The conformation of each fragment can be computed based on the preceding protocol. Finally, we assemble all fragments by pure translations based on sparse NOE distance constraints.

Time Complexity Let nn denote the number of residue in the protein. The dividing step takes O(n)O(n) time. The structure determination of each fragment takes O(nmexp⁡(m))O(\frac{n}{m} \exp(m)) , where mm is the maximum length of fragments. The assembling step runs in O(n)O(n) time. Since m=O(1)m = O(1) [8], the total running time is O(n)O(n) . This algorithm is therefore optimal in terms of the geometric and combinatorial complexity nn . See chapters 15 through 18 and Wang et al. [8].

Open Problem RDCs are a geometric measurement similar to the angular restraints with error γ\gamma in figure 36.1 and section 36.2.1. Use SDP and the concept of distance geometry with angle restraints to model RDC-based structure determination. The angular restraints come from RDCs, and the distance restraints from NOEs. What is the best algorithm you can derive, in terms of complexity? Implement and test your algorithm, using both synthetic and real NMR data.

References

  • [1] M. Badoiu, and E. D. Demaine, M. T. Hajiaghayi, and P. Indyk. Low-dimensional embedding with extra information. Proceedings of the Twentieth Annual Symposium on Computational Geometry, 2004.
  • [2] P. Biswas and T. Lian and T. Wang, and Y. Ye. Semidefinite Programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks (TOSN), (2006).
  • [3] Bernard Chazelle, Carl Kingsford, and Mona Singh. A semidefinite programming approach to side-chain positioning with new rounding strategies. INFORMS Journal on Computing 16;4(2004): 380–392.
  • [4] R.M. Freund, Introduction to Semidefinite Programming. Sloan School, MIT, DSPACE online publication (1999) accessed: 2009, url: http://dspace.mit.edu/bitstream/handle/1721.1/35259/15-094Spring-2002/NR/rdonlyres/Sloan-School-of-Management/15-094Systems-Optimization-Models-and-ComputationSpring2002/A849A5EB-FBF7-4631-8B52-CBBC667E74EB/0/sdpintro.pdf
  • [5] N. A. Pierce and E. Winfree. Protein design is NP-hard. Protein Engineering, 15;10(2003):779–782, 2002.
  • [6] J. B. Saxe. Embeddability of weighted graphs in kk -space is strongly NP-hard. Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, (1979):480–489.
  • [7] 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.
  • [8] L. Wang, R. R. Metta, and B. R. Donald. A polynomial-time algorithm for de novo protein backbone structure determination from nuclear magnetic resonance data. Journal of Computational Biology 13;7(2006):1267–1288.