On Sufficient Statistics of Least-Squares Superposition of Vector Sets

LA home
Computing
Publications
 RECOMB

also see
Bioinf
 protein
and
 AlgDS
  Numerical
   Superposition

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

RECOMB 2014, Springer Verlag, LNBI 8394, pp.144-159, 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]

www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Friday, 24-Nov-2017 04:30:59 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.