21st EANN 2020, 5 -7 June 2020, Greece

Computational Complexity of Kabsch and Quaternion Based Algorithms for Molecular Superimposition in Computational Chemistry

Rafael Doležal, Katerina Fronckova, Ayca Kirimtat, Ondrej Krejcar


  This work deals with analysis of Kabsch and quaternion algorithms, which may be used for 3D superimposition of molecules by rigid roto-translation in computational chemistry and biology. Both algorithms, which are very im-portant for in silico drug design, were studied from the point of view of their non-trivial mathematical structure. Their computational complexity was in-vestigated by superimposition of various random pseudo-molecules with 2 – 100,000 atoms in Matlab. It was found that both proposed algorithm imple-mentations exhibit the same asymptotic time computational complexity of O(n), with the quaternion algorithm involving a higher number of floating-point operations (FLOPs) and showing lower computational performance in terms of serial CPU time.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.