en>Niceguyedc: WPCleaner v1.33 - Repaired 1 link to disambiguation page - (You can help) - Subfield

2014-08-17T19:25:23Z

WPCleaner v1.33 - Repaired 1 link to disambiguation page - (You can help) - Subfield

en>Brad7777: removed Category:Theorems in algebra; added Category:Theorems in abstract algebra using HotCat

2012-01-31T21:13:00Z

removed Category:Theorems in algebra; added Category:Theorems in abstract algebra using HotCat

New page

The '''Kabsch algorithm''', named after [[Wolfgang Kabsch]], is a method for calculating the optimal [[rotation matrix]] that minimizes the [[RMSD]] ([[root mean square]]d deviation) between two paired sets of points. It is useful in graphics, [[cheminformatics]] to compare molecular structures, and also [[bioinformatics]] for comparing [[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 ==

The algorithm starts with two sets of paired points, ''P'' and ''Q''. Each set of points can be represented as an ''N''×3 [[matrix (mathematics)|matrix]]. The first row is the coordinates of the first point, the second row is the coordinates of the second point, the ''N''th row is the coordinates of the ''N''th point.

:<math>\begin{pmatrix}
x_1 & y_1 & z_1 \\
x_2 & y_2 & z_2 \\
\vdots & \vdots & \vdots \\
x_N & y_N & z_N \end{pmatrix}</math>

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 consist of calculating a [[covariance matrix]] ''A''. In matrix notation,

:<math> A = P^TQ \, </math>

or, using summation notation,

:<math> A_{ij} = \sum_{k = 1}^N P_{ki} Q_{kj}, </math>

=== Computation of the optimal rotation matrix ===
It is possible to calculate the optimal rotation ''U'' based on the matrix formula <math> U = (A^T A)^{1/2}A^{-1} </math> but implementing a numerical solution to this formula becomes complicated when all special cases are accounted for (for example, the case of ''A'' not having an inverse).

If [[singular value decomposition]] (SVD) routines are available, the optimal rotation, ''U'', can be calculated using the following simple algorithm.

First, calculate the SVD of the covariance matrix ''A''.

:<math> A = VSW^T \, </math>

Next, decide whether we need to correct our rotation matrix to ensure a right-handed coordinate system

:<math> d = \operatorname{sign}(\det(W V^T)) \, </math>

Finally, calculate our optimal rotation matrix, ''U'', as

:<math> U = W \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & d \end{pmatrix} V^T </math>

Coutsias, Seok, and Dill<ref name=Coutsias2004>{{cite journal | author = Coutsias EA, Seok C, Dill KA | title = Using quaternions to calculate RMSD | journal = J Comput Chem | volume = 25 | issue = 15 | pages = 1849–1857 | year = 2004 | pmid = 15376254 | doi = 10.1002/jcc.20110}}</ref> have found an equivalent method that uses [[quaternion]]s.

=== Generalizations ===

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

== External links ==
This SVD algorithm is described in more detail at http://cnx.org/content/m11608/latest/

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

A free [[PyMol]] plugin easily implementing Kabsch is [http://www.pymolwiki.org/index.php/Cealign Cealign]. [[Visual Molecular Dynamics|VMD]] uses the Kabsch algorithm for its alignment.

A [[Python_(programming_language)|Python]] script is available at http://github.com/charnley/rmsd

== See also ==

[[Wahba's problem|Wahba's Problem]]

== References ==
{{reflist}}

* Kabsch, Wolfgang, (1976) "A solution for the best rotation to relate two sets of vectors", ''Acta Crystallographica'' '''32''':922. {{doi|10.1107/S0567739476001873}} with a correction in Kabsch, Wolfgang, (1978) "A discussion of the solution for the best rotation to relate two sets of vectors", "Acta Crystallographica", "A34", 827–828 {{doi|10.1107/S0567739478001680}}

* Lin Ying-Hung, Chang Hsun-Chang, Lin Yaw-Ling (2004) "A Study on Tools and Algorithms for 3-D Protein Structures Alignment and Comparison", ''International Computer Symposium'', December 15–17, Taipei, Taiwan.

[[Category:Bioinformatics algorithms]]

Isomorphism extension theorem - Revision history

en>Niceguyedc: WPCleaner v1.33 - Repaired 1 link to disambiguation page - (You can help) - Subfield

en>Brad7777: removed Category:Theorems in algebra; added Category:Theorems in abstract algebra using HotCat