On sufficient statistics of least-squares superposition of vector sets

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

    Research output: Contribution to journalArticleResearchpeer-review

    1 Citation (Scopus)


    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.
    Original languageEnglish
    Pages (from-to)487-497
    Number of pages11
    JournalJournal of Computational Biology
    Issue number6
    Publication statusPublished - 2015


    • RMSD
    • Superposition
    • Alignment
    • Sufficient statistics
    • On sufficient statistics of least-squares superposition of vector sets

      Konagurthu, A. S., Kasarapu, P., Allison, L., Collier, J. H. & Lesk, A. M., 2014, Research in Computational Molecular Biology: 18th Annual International Conference, RECOMB 2014, Pittsburgh, PA, USA, April 2-5, 2014, Proceedings. Sharan, R. (ed.). Cham [Switzerland]: Springer, p. 144 - 159 16 p.

      Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

      5 Citations (Scopus)

    Cite this