Skip to content Skip to navigation
Summary: This module introduces students to the inverse kinematics of manipulators and its relevance to problems in computational structural biology.
Note: You are viewing an old version of this document. The latest version is available here.
The math involved in solving inverse kinematics requires some background in linear algebra, specifically in the anatomy and application of transformation matrices. The links provided in this section should provide enough mathematical background to understand the rest of this module and eventually write a simple protein manipulation program.
Many globular proteins have a relatively stable, inflexible core region, consisting of tightly arranged secondary structure elements, and are less compact and more flexible at the surface, where, among other effects, solvent molecules may cause loose chains and loops to swing freely. One consequence of this flexibility is that experimental structure determination methods may have difficulty resolving the positions of surface loops of the protein chain. The positions of the atoms in those loops may be so incosistent that no single position relative to the core dominates, and so their positions cannot be determined by experiment.
When this happens, we are left with partial protein structures, with segments of the protein chain missing. We know the amino acid sequence of the missing sequence, and where its endpoints join the known part of the structure. Given this information, we would like to be able to reconstruct feasible structures for the missing segment such that the endpoints join to the known structure at the proper points, and such that all constraints of bond lengths and angles are satisfied. This is an instance of the Loop Closure Problem, and it is intimately related to the inverse kinematics problem in robotics.
Inverse kinematics is the problem of finding the right values for the underlying degrees of freedom, in the case of proteins, of the dihedral angles, so that the manipulated chain satisfies certain spatial constraints. For example, in some applications, it is necessary to find rotations that can steer certain atoms to desired locations in space. To achieve a particular function, protein regions sometimes have to undergo concerted motion where atoms move together in order to locate themselves near another protein or molecule. The motion of atoms is spatially constrained because they have to assume specific target locations in space. However, since atoms must move together in order not to break bonds by their motion, it is easier to model their motion in dihedral angle space, where bond lengths and bond angles are fixed. This parameterization of protein motion, called the idealized or rigid geometry model, is discussed in Representing Proteins in silico: Data Structures and Kinematics.
In applying inverse kinematics algorithms to proteins, we are taking advantage of a striking similarity between organic molecules and robotic manipulators (robot arms) in terms of how they move. As robot manipulators have joints, proteins have atoms. As robot manipulators have links that connect their joints, proteins have bonds that connect their atoms. The similarity between proteins and robots makes it possible for us to apply to proteins a large existing literature of solutions to the Inverse Kinematics problem, developed in the context of robot manipulators (robotic arms).
Before we proceed with some simple inverse kinematics examples, note that inverse kinematics is the inverse of the forward kinematics problem. Therefore, an immediate attempt to solve the inverse kinematics problem would be by inverting forward kinematics equations.
Let's illustrate how to solve the inverse kinematics problem for robot manipulators on a simple example. The figure below shows a simple planar robot with two arms. The underlying degrees of freedom of this robot are the two angles dictating the rotation of the arms. These are illustrated in the figure below. The inverse kinematics question in this case would be: What are the values for the degrees of freedom so that the end effector of this robot (the tip of the last arm) lies at position (x,y) in the two-dimensional Cartesian space? Try to write down the forward kinematics equations that relate (x,y) to the two rotational degrees of freedom, then try to solve these equations. The solutions will give you an answer to the inverse kinematics problem for this robot.
|
Given (x, y) target position for end-effector of the robot, what are the solutions for the two rotational (θ) degrees of freedom?
You can compare your answer with the derivation steps below.
| Simple Example Solved |
|---|
 |
While the above example offers equations that are easy to solve, general inverse kinematics problems require solving systems of nonlinear equations for which there are no general algorithms. Some inverse kinematics problems cannot be solved analytically because mathematical singularities (such as undefined sines and cosines, or division by 0) arise during the computation. In robotics, it is sometimes possible to design systems to have solvable inverse kinematics, but in the general case, we must rely on approximation methods in order to keep the problem tractable, or, in some cases, even solvable. For examples on how to address inverse kinematics in particular systems, please read chapter 4 of [1].
| More Realistic Example |
|---|
 |
Inverse kinematics methods are categorized into two main groups:
It is known that for manipulators with no more than six degrees of freedom, there is a finite number of solutions to the inverse kinematics problem [1]. There is, however, no analytical method that can find these solutions for all types of manipulators. For manipulators with only revolute joints, which is the case for biomolecules with idealized geometry, the number of unique solutions is at most 16, when the number of degrees of freedom does not exceed six [6]. An efficient solution was proposed in [8] and later applied to the conformational analysis of small molecular chains [9], [10]. Methods based on curve approximation were proposed in [7] for the inverse kinematics of hyper-redundant robots, where the number of regularly distributed joints is very large.
Specialized solutions to inverse kinematics in biochemistry appeared as early as 1970 [12], where fragments of up to 6 degrees of freedom were predicted by solving a set of polynomial equations representing geometric transformations. These equations were applied to building tripeptide loops [12] under the ideal geometry assumption. Later work [15], [13], [10], [14] offered efficient analytical solutions for three consecutive residues through spherical geometry and polynomial equations. Bounding inverse kinematic solutions for chains with no more than six degrees of freedom within small intervals was applied in the context of drug design [11]. A new formulation that extends the domain of solutions to any three residues, not necessarily consecutive, and with arbitrary geometry, was recently proposed [16]. Current work that pushes the dimensionality limit from six to nine degrees of freedom makes use of an efficient subdivision of the solution space [17].
Currently only optimization-based solutions are considered appropriate for accommodating chains with arbitrary numbers of degrees of freedom. Two well-known optimization-based inverse kinematics solutions that iteratively solve a system of equations until loops are closed are Random Tweak [18], [19] and Cyclic Coordinate Descent (CCD) [3], [4], [5]. Both methods are based on iteratively setting the dihedral degrees of freedom of a fragment or kinematic chain until 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 numerically unstable. In addition to not being free from mathematical singularities, random tweak does not allow additional constraints on individual residues because modifications to dihedral angles are introduced all at once, with a strong dependence of each dihedral proposed change on all the others. Additional constraints on the dihedrals may result in the unpredictable motion of a feature atom away from rather than toward its target position.
Avoiding the use of the Jacobian, CCD is computationally inexpensive, numerically stable, and free from singularities. This method avoids the interdependence of dihedral angles by adjusting only a single degree of freedom at a time, which allows for additional constraints on dihedral angles with a predictable motion of feature atoms towards their target positions. First introduced in the context of non-linear programming [3] , this method was applied to robotics [4], and later was applied to the loop closure problem for proteins[5].
CCD tries to find an optimal angle by which to rotate a single bond so as to steer a desired atom towards its target position. We will explain a solution where we will try to find an optimal angle by which to steer three atoms simultaneously. We first define their current positions M and their target positions F, as shown in the figure below. The goal is to minimize the Euclidean distance between the current and the target positions for all three atoms simultaneously. That is why we define an objective function S that sums the squared distances per atom.
|
tan(α α . However, an expression for the tangent does not provide a unique value for the angle. This is a consequence of the fact that the derivative of S set to 0 corresponds not 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 the second order derivative of S is greater than 0. This is more cumbersome. There is a way to avoid doing such calculations by realizing that the formula we received for S in terms of the angle we want to solve for, can be rewritten as shown below. 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.
|
Unlike classic inverse-kinematics solutions that use Jacobian matrices [18], [19], or general numerical approaches, CCD is free of singularities and does not depend on initial guesses for solutions. Compared to inverse kinematics techniques with optimization that suffer from high computational times, CCD is computationally fast. Unlike other methods such as random tweak, CCD gives predictable behavior and suffers from no anomalies when additional constraints are added to the dihedrals (e.g. constraints imposed by the physico-chemical forces on the protein). Such properties make CCD very appealing.
When solving for long polypeptide chains, one needs to define the set of rotatable dihedrals that can be solved for through CCD. These dihedrals can then be used to rotate and therefore steer the desired atom towards its target position. A straighforward implementation proceeds down the rotatable dihedral angles according to a predetermined order finding maximum angle values by which to rotate the current dihedral so that the desired atom gets as close as possible to its target position. Once such a value is computed, one can update the conformation of the polypeptide chain through forward kinematics. To learn more about the application of CCD to resolving partial protein structures, such as loop closure, please refer to [5]. Another interesting application of CCD to complete partially resolved crystallograhic data is Itay Lotan's thesis .
More about this module: Metadata | Downloads | Version History
This work is licensed by Lydia E. Kavraki under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.
Last edited by Hernan Stamati on Mar 29, 2006 3:58 pm -0600.
