The Kabsch algorithm, also known as the Kabsch-Umeyama algorithm,[1] 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)).
We want to find the transformation from Q to P. For simplicity, we will consider the three-dimensional case (
It is possible to calculate the optimal rotation R based on the matrix formula but implementing a numerical solution to this formula becomes complicated when all special cases are accounted for (for example, the case of H not having an inverse).
If singular value decomposition (SVD) routines are available the optimal rotation, R, can be calculated using the following algorithm.
First, calculate the SVD of the covariance matrix H, where U and V are orthogonal and
Next, record if the orthogonal matrices contain a reflection, Finally, calculate our optimal rotation matrix R as This R minimizes
Alternatively, optimal rotation matrix can also be directly evaluated as quaternion.
[2][3][4][5] 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.
[6] In 2002 a generalization for the application to probability distributions (continuous or not) was also proposed.
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.
A free PyMol plugin easily implementing Kabsch is [1].
(This previously linked to CEalign [2], but this uses the Combinatorial Extension (CE) algorithm.)
The FoldX modeling toolsuite incorporates the Kabsch algorithm to measure RMSD between Wild Type and Mutated protein structures.