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