Kabsch algorithm

Template:Short description The Kabsch algorithm, also known as the Kabsch-Umeyama algorithm, named after Wolfgang Kabsch and Shinji Umeyama, is a method for calculating the optimal rotation matrix that minimizes the RMSD (root mean squared deviation) between two paired sets of points. It is useful for point-set registration in computer graphics, and in cheminformatics and bioinformatics to compare molecular and protein structures (in particular, see root-mean-square deviation (bioinformatics)).

The algorithm only computes the rotation matrix, but it also requires the computation of a translation vector. When both the translation and rotation are actually performed, the algorithm is sometimes called partial Procrustes superimposition (see also orthogonal Procrustes problem).

Description

Let Template:Mvar and Template:Mvar be two sets, each containing Template:Mvar points in ${ℝ}^n$. We want to find the transformation from Template:Mvar to Template:Mvar. For simplicity, we will consider the three-dimensional case ($n=3$). The sets Template:Mvar and Template:Mvar can each be represented by Template:Math matrices with the first row containing the coordinates of the first point, the second row containing the coordinates of the second point, and so on, as shown in this matrix:

$$\left(\begin{array}{ccc}{x}_1& y_1& z_1\\ x_2& y_2& z_2\\ ⋮& ⋮& ⋮\\ x_N& y_N& z_N\end{array}\right)$$

The algorithm works in three steps: a translation, the computation of a covariance matrix, and the computation of the optimal rotation matrix.

Translation

Both sets of coordinates must be translated first, so that their centroid coincides with the origin of the coordinate system. This is done by subtracting the centroid coordinates from the point coordinates.

Computation of the covariance matrix

The second step consists of calculating a matrix Template:Mvar. In matrix notation,

$H=P^{𝖳}Q$

or, using summation notation,

$H_{ij}=\sum _{k=1}^N{P}_{ki}{Q}_{kj},$

which is a cross-covariance matrix when Template:Mvar and Template:Mvar are seen as data matrices.

Computation of the optimal rotation matrix

It is possible to calculate the optimal rotation Template:Mvar based on the matrix formula

$R={\left(H^{𝖳}H\right)}^{\frac{1}{2}}{H}^{-1},$

but implementing a numerical solution to this formula becomes complicated when all special cases are accounted for (for example, the case of Template:Mvar not having an inverse).

If singular value decomposition (SVD) routines are available the optimal rotation, Template:Mvar, can be calculated using the following algorithm.

First, calculate the SVD of the covariance matrix Template:Mvar,

$H=U\mathrm{\Sigma }{V}^{𝖳}$

where Template:Mvar and Template:Mvar are orthogonal and $\mathrm{\Sigma }$ is diagonal. Next, record if the orthogonal matrices contain a reflection,

$d=\det \left(U{V}^{𝖳}\right)=\det (U)\det (V).$

Finally, calculate our optimal rotation matrix Template:Mvar as

$R=U\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& d\end{array}\right)V^{𝖳}.$

This Template:Mvar minimizes $\sum _{k=1}^N|R{q}_k-p_k|$, where $q_k$ and $p_k$ are rows in Template:Mvar and Template:Mvar respectively.

Alternatively, optimal rotation matrix can also be directly evaluated as quaternion. This alternative description has been used in the development of a rigorous method for removing rigid-body motions from molecular dynamics trajectories of flexible molecules. In 2002 a generalization for the application to probability distributions (continuous or not) was also proposed.

Generalizations

The algorithm was described for points in a three-dimensional space. The generalization to Template:Mvar dimensions is immediate.

External links

This SVD algorithm is described in more detail at https://web.archive.org/web/20140225050055/http://cnx.org/content/m11608/latest/

A Matlab function is available at http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

A C++ implementation (and unit test) using Eigen

A Python script is available at https://github.com/charnley/rmsd. Another implementation can be found in SciPy.

A free PyMol plugin easily implementing Kabsch is [1]. (This previously linked to CEalign [2], but this uses the Combinatorial Extension (CE) algorithm.) VMD uses the Kabsch algorithm for its alignment.

The FoldX modeling toolsuite incorporates the Kabsch algorithm to measure RMSD between Wild Type and Mutated protein structures.

See also

• Wahba's Problem
• Orthogonal Procrustes problem

References

• Template:Cite journal
  • With a correction in Template:Cite journal
• Template:Cite conference
• Template:Cite journal