Kabsch algorithm


The Kabsch algorithm, named after Wolfgang Kabsch, is a method for calculating the optimal rotation matrix that minimizes the RMSD between two paired sets of points. It is useful in graphics, cheminformatics to compare molecular structures, and also bioinformatics for comparing protein structures.
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.

Description

The algorithm for the rotation of into starts with two sets of paired points, and. Each set of points can be represented as an matrix. The first row is the coordinates of the first point, the second row is the coordinates of the second point, the th row is the coordinates of the th point.
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 from the point coordinates the coordinates of the respective centroid.

Computation of the covariance matrix

The second step consists of calculating a matrix. In matrix notation,
or, using summation notation,
which is a cross-covariance matrix when and are seen as data matrices.

Computation of the optimal rotation matrix

It is possible to calculate the optimal rotation based on the matrix formula
but implementing a numerical solution to this formula becomes complicated when all special cases are accounted for.
If singular value decomposition routines are available, the optimal rotation,, can be calculated using the following simple algorithm.
First, calculate the SVD of the covariance matrix.
Next, decide whether we need to correct our rotation matrix to ensure a right-handed coordinate system
Finally, calculate our optimal rotation matrix,, as
The optimal rotation matrix can also be expressed in terms of quaternions. This alternative description was recently 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 was also proposed.

Generalizations

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