Arun S. Konagurthu, Parthan Kasarapu, Lloyd Allison, James H. Collier, and Arthur M. Lesk

RECOMB 2014, Springer Verlag, LNBI 8394, pp.144-159, doi:10.1007/978-3-319-05269-4_11, 2014.

Superposition by orthogonal transformation of vector sets by minimizing the least-squares error is a fundamental task in many areas of science, notably in structural molecular biology. Its widespread use for structural analyses is facilitated by exact solns of this problem, computable in linear time. However, in several of these analyses it is common to invoke this superposition routine a very large number of times, often operating (through addition or deletion) on previously superposed vector sets. This paper derives a set of sufficient statistics for the least-squares orthogonal transformation problem. These sufficient statistics are additive. This property allows for the superposition parameters (rotation, translation, & root mean square deviation) to be computable as constant time updates from the statistics of partial solutions. We demonstrate that this results in a massive speed up in the computational effort, when compared to the method that recomputes superpositions ab initio. Among others, protein structural alignment algorithms stand to benefit from our results.

[doi:10.1007/978-3-319-05269-4_11]