Kabsch algorithm

From Wikipedia, the free encyclopedia

The Kabsch algorithm is a method for calculating the optimal alignment of two sets of points. It is useful in graphics, and also in bioinformatics for calculating the RMSD (root mean squared deviation) between two protein structures.

The algorithm works by calculating a matrix of multiplied components. The destination matrix, A, is a 3 × 3 matrix with x, y and z components for each side. The source is two sets of paired points, P and Q.

Aij =	∑	PkiQkj
	k

(sum over the points and multiply components).

The formula is

(A^tA)^{1 / 2}A ^{− 1}

or take the square root of the product of the transpose of A and A itself, then multiply by the inverse of A.

The algorithm calculates only the rotation matrix. Both sets of coordinates must be transformed to their centroid first.

C source is available at http://www.personal.leeds.ac.uk/~bgy1mm/Bioinformatics/rmsd.html

A free PyMol plugin easily implementing Kabsch is Cealign.

[edit] References

• Kabsch, Wolfgang, (1976) "A solution of the best rotation to relate two sets of vectors", Acta Crystallographica 32:922. doi:10.1107/S0567739476001873

• 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, Dec 15-17, Taipei, Taiwan.