<< Chapter < Page Chapter >> Page >

Inverse kinematics methods with optimization

Currently, optimization-based solutions are considered most appropriate for accommodating chains with arbitrary numbers of degrees of freedom. Twowell-known optimization-based inverse kinematics solutions that iteratively solve a system of equations until loops are closed are Random Tweak , and Cyclic Coordinate Descent (CCD) , , . Both methods are based on iteratively setting the dihedral degrees of freedom of a fragment or kinematic chainuntil the end effector (atom for a protein) reaches a target position.

Random tweak relies on the computation of the Jacobian (a high-dimensional analog of the derivative of a function on real numbers), a process that is computationally expensive and numericallyunstable. In addition to not being free from mathematical singularities, random tweak does not allow additional constraintson individual residues because modifications to dihedral angles are introduced all at once, with a strong dependence of each dihedralproposed change on all the others. Additional constraints on the dihedrals may result in the unpredictable motion of a feature atomaway from rather than toward its target position.

Avoiding the use of the Jacobian, CCD is computationally inexpensive, numerically stable, and free from singularities. CCDavoids the interdependence of dihedral angles by adjusting only a single degree of freedom at a time. This allows for additional constraints on dihedral angles witha predictable motion of the end effector towards the target position. First introduced in the context of non-linearprogramming , CCD was found applications in the robotics community, and later in the structural biology community in the context of the loop closure problem for proteins .

Cyclic coordinate descent and its application to proteins

CCD tries to find an optimal angle by which to rotate a single bond so as to steer a desired atom towards itstarget position. When applying CCD to find dihedral angles of a fragment of the polypeptide chain so that the ends of the fragmentconnect properly with the rest of the chain, it is important to steer not just one atom of the end of the fragment, but the threebackbone atoms of the end simultaneously. Finding values to the dihedral angles that steer the three backbone atoms of the end ofthe fragment simultaneously to their target positions guarantees that the end of the fragment will assume both its target positionand orientation in space. We will explain how to find optimal values to the dihedral angles of a fragment by which to simultaneouslysteer the three backbone atoms of the end of the fragment to their target positions. We first define their current positions M andtheir target positions F, as shown in the figure below. The goal is to minimize the Euclidean distance between the current and thetarget positions for all three atoms simultaneously.

In order to find the optimal angle by which to rotate a particular bond, we can define an objective function S that we wish to minimize. We propose a value for S that sums the square of the deviations between the final position of the atoms after the rotation (M) and the desired positions (F). Using this nomenclature, the squared norm of the vector M-F (denoted FM) has precisely this value for each of the three atoms, so we can sum the three contributions to S. The FM vectors can be defined relative to an origin O located along the axis of rotation, which will simplify the math, since the rotation is two-dimensional when working on the plane perpendicular to the axis of rotation. O can be computed by projecting the current position of the atom, M, onto the rotation axis. It is convenient to decompose OM for each feature atom into two components (along the r and s local axes), in order to allow its expression in terms of the angle being rotated (using cosine and sine). This way, the distance between the atoms and their target positions will be only a function of the fixed (rotatable bond) atoms and the angle to rotate, which remains the only variable and the problem can be solved.

Ccd schematics

Find optimal dihedral rotation for the current bond so that all three desired atoms reach their target positions.

Finding optimal angle

Since S is defined as the sum of squared distances between current positions and target positions, steering these three atoms totheir target positions requires minimizing S. Therefore, the optimal dihedral rotation can be found by minimizing S.
Schematics of Cyclic Coordinate Descent
The question then becomes that of finding a rotation along therotation axis O, shown in the figure, that minimizes S. First, we need to define S as a function of the angle we are trying to find. Doing sois not hard, since rotation by this angle is a two-dimensional rotation. In the figure above we have shown how the position of anatom can be updated through a two-dimensional rotation by the angle around the rotation axis. In this way we obtain an expression thatrelates S to the angle we want to find. Since this angle has to minimize S, it has to provide a solution to the first order derivativeof S set to 0. This is shown below in Figure 5. Simplifying the expression for the first order derivative of S set to 0 gives us aformula for tan( α ) . CCD is a very efficient method due to the fact that it obtains the value for α analytically. However, an expression for thetangent does not provide a unique value for the angle. This is a consequence of the fact that the derivative of S set to 0 correspondsnot only to minima, but also to local maxima. In order to find the angle that indeed minimizes S, one would have to make sure that thesecond order derivative of S is greater than 0. This is more cumbersome. There is a way to avoid doing such calculations byrealizing that the formula we received for S in terms of the angle we want to solve for, can be rewritten as shown in Figure 5. In this way,one can obtain a value for both the cosine and the sine of the angle, which now uniquely determines the optimal angle.

Ccd solution

Posing a minimization procedure reveals the value for the optimal angle.

Better solution

The correct quadrant can be determined by rewriting S.
Solution to the minimization of S

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Geometric methods in structural computational biology. OpenStax CNX. Jun 11, 2007 Download for free at http://cnx.org/content/col10344/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Geometric methods in structural computational biology' conversation and receive update notifications?

Ask