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: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

    5 Citations (Scopus)

    Abstract

    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 solutions 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, and 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.
    Original languageEnglish
    Title of host publicationResearch in Computational Molecular Biology
    Subtitle of host publication18th Annual International Conference, RECOMB 2014, Pittsburgh, PA, USA, April 2-5, 2014, Proceedings
    EditorsRoded Sharan
    Place of PublicationCham [Switzerland]
    PublisherSpringer
    Pages144 - 159
    Number of pages16
    ISBN (Electronic)9783319052694
    ISBN (Print)9783319052687
    DOIs
    Publication statusPublished - 2014
    EventInternational Conference on Computational Molecular Biology 2014 - Pittsburgh, United States of America
    Duration: 2 Apr 20145 Apr 2014
    Conference number: 18th
    http://murphylab.web.cmu.edu/compbio/recomb/

    Conference

    ConferenceInternational Conference on Computational Molecular Biology 2014
    Abbreviated titleRECOMB 2014
    CountryUnited States of America
    CityPittsburgh
    Period2/04/145/04/14
    Internet address

    Cite this

    Konagurthu, A. S., Kasarapu, P., Allison, L., Collier, J. H., & Lesk, A. M. (2014). On sufficient statistics of least-squares superposition of vector sets. In R. Sharan (Ed.), Research in Computational Molecular Biology: 18th Annual International Conference, RECOMB 2014, Pittsburgh, PA, USA, April 2-5, 2014, Proceedings (pp. 144 - 159). Springer. https://doi.org/10.1007/978-3-319-05269-4_11