# The Quaternion Characteristic Polynomial method: Ultrafast determination of the minimum RMSD and the optimal least-squares rotation matrix

The **QCP** method is the fastest method known for determining the minimum RMSD between two structures and for determining the optimal least-squares rotation matrix.
Least-squares superposition methods find the rotation matrix that minimizes the RMSD.
The most common algorithms use an eigendecomposition, a singular value decomposition, or an inversion of a small "key" matrix (of rank 3 or 4).
The **QCP** method avoids the costly matrix decomposition by taking advantage of special properties of the quaternion representation of rotations and of the characteristic polynomial of the 4×4 "key" matrix.

In the **QCP** method, the RMSD is first evaluated by solving for the most positive eigenvalue of the 4×4 key matrix using a Newton-Raphson algorithm that quickly finds the largest root (eigenvalue) from the characteristic polynomial.
The minimum RMSD is then easily caclulated from the largest eigenvalue.
If only the RMSD is required (i.e., the rotation matrix is not needed), this method is orders of magnitude faster than the most efficient competing methods.

If the optimal rotation matrix is also desired, then the best rotation is given by the corresponding eigenvector, which we calculate from a row of the adjoint matrix.
Finding the rotation via the **QCP** method is up to an order of magnitude faster than matrix decomposition algorithms.

These methods have several advantages:
(i) the time required to calculate the rotation matrix is independent of the system size after a special 3×3 matrix is constructed from the coordinates,
(ii) no special cases need to be handled separately, and
(iii) the approach is extremely fast, straightforward, and robust, since there is no expensive matrix inversion or decomposition.
To our knowledge, the **QCP** algorithm is by far the fastest method currently available for superpositioning macromolecules.
The algorithm is particularly useful for high-throughput analyses of molecular conformations, whenever finding the RMSD and/or the optimal rotation is a computational bottleneck.

## Citations

**
Liu P, Agrafiotis DK, & Theobald DL (2011)
**

Reply to comment on: "Fast determination of the optimal rotation matrix for macromolecular superpositions."

*
Journal of Computational Chemistry
*
32(1):185-186.
* [Open Access]*

**
Liu P, Agrafiotis DK, & Theobald DL (2010)
**

"Fast determination of the optimal rotation matrix for macromolecular superpositions."

*
Journal of Computational Chemistry
*
31(7):1561-1563.
* [Open Access]*

**
Douglas L Theobald (2005)
**

"Rapid calculation of RMSDs using a quaternion-based characteristic polynomial."

*
Acta Crystallogr A
*
61(4):478-480. [*Open Access*,
pdf]

##
Latest Version -
*
QCProt 1.5 (2016, July 13)
*

UNIX C source code, licensed under a BSD open source license.

Requires an ANSI C compiler (preferably
GNU GCC) to compile.

Download the tgz compressed archive