title: Efficient computation of root mean square deviations under rigid transformations.
abstract: The computation of root mean square deviations (RMSD) is an important step in many bioinformatics applications. If approached naively, each RMSD computation takes time linear in the number of atoms. In addition, a careful implementation is required to achieve numerical stability, which further increases runtimes. In practice, the structural variations under consideration are often induced by rigid transformations of the protein, or are at least dominated by a rigid component. In this work, we show how RMSD values resulting from rigid transformations can be computed in constant time from the protein's covariance matrix, which can be precomputed in linear time. As a typical application scenario is protein clustering, we will also show how the Ward-distance which is popular in this field can be reduced to RMSD evaluations, yielding a constant time approach for their computation.
authors.affiliation: Center for Bioinformatics, Saarland University, Saarbrücken, 66041, Germany.
authors.forename: Anna K
authors.initials: AK
authors.lastname: Hildebrandt
authors.affiliation: Max Planck Institute for Informatics, Saarbrücken, 66123, Germany.
authors.forename: Matthias
authors.initials: M
authors.lastname: Dietzen
authors.affiliation: Max Planck Institute for Informatics, Saarbrücken, 66123, Germany.
authors.forename: Thomas
authors.initials: T
authors.lastname: Lengauer
authors.affiliation: Center for Bioinformatics, Saarland University, Saarbrücken, 66041, Germany.
authors.forename: Hans-Peter
authors.initials: HP
authors.lastname: Lenhof
authors.affiliation: Institute for Informatics, Johannes-Gutenberg-University Mainz, Mainz, 55128, Germany.
authors.forename: Ernst
authors.initials: E
authors.lastname: Althaus
authors.affiliation: Institute for Informatics, Johannes-Gutenberg-University Mainz, Mainz, 55128, Germany.
authors.forename: Andreas
authors.initials: A
authors.lastname: Hildebrandt
mesh_terms: D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry
chemical_list: D011506:Proteins
keywords: molecular modeling; protein docking; root mean square deviation computation