title: On sufficient statistics of least-squares superposition of vector sets.
abstract: The problem of superposition of two corresponding vector sets by minimizing their sum-of-squares error under orthogonal transformation is a fundamental task in many areas of science, notably structural molecular biology. This problem can be solved exactly using an algorithm whose time complexity grows linearly with the number of correspondences. This efficient solution has facilitated the widespread use of the superposition task, particularly in studies involving macromolecular structures. This article formally derives a set of sufficient statistics for the least-squares superposition problem. These statistics are additive. This permits a highly efficient (constant time) computation of superpositions (and sufficient statistics) of vector sets that are composed from its constituent vector sets under addition or deletion operation, where the sufficient statistics of the constituent sets are already known (that is, the constituent vector sets have been previously superposed). This results in a drastic improvement in the run time of the methods that commonly superpose vector sets under addition or deletion operations, where previously these operations were carried out ab initio (ignoring the sufficient statistics). We experimentally demonstrate the improvement our work offers in the context of protein structural alignment programs that assemble a reliable structural alignment from well-fitting (substructural) fragment pairs. A C++ library for this task is available online under an open-source license.
authors.affiliation: 1Clayton School of Computer Science and Information Technology, Faculty of Information Technology, Monash University, Clayton, Australia.
authors.forename: Arun S
authors.initials: AS
authors.lastname: Konagurthu
authors.affiliation: 1Clayton School of Computer Science and Information Technology, Faculty of Information Technology, Monash University, Clayton, Australia.
authors.forename: Parthan
authors.initials: P
authors.lastname: Kasarapu
authors.affiliation: 1Clayton School of Computer Science and Information Technology, Faculty of Information Technology, Monash University, Clayton, Australia.
authors.forename: Lloyd
authors.initials: L
authors.lastname: Allison
authors.affiliation: 1Clayton School of Computer Science and Information Technology, Faculty of Information Technology, Monash University, Clayton, Australia.
authors.forename: James H
authors.initials: JH
authors.lastname: Collier
authors.affiliation: 2The Huck Institute of Genomics, Proteomics and Bioinformatics, Pennsylvania State University, University Park, Pennsylvania.|3Department of Biochemistry and Molecular Biology, Pennsylvania State University, University Park, Pennsylvania.
authors.forename: Arthur M
authors.initials: AM
authors.lastname: Lesk
mesh_terms: D000465:Algorithms; D016018:Least-Squares Analysis; D008958:Models, Molecular; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods
chemical_list: D011506:Proteins
keywords: RMSD; alignment; sufficient statistics; superposition