Abstract
This work deals with the 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 important for in silico drug design, were studied from the point of view of their non-trivial mathematical structure. Their computational complexity was investigated by a superimposition of various random pseudo-molecules with 2 – 100,000 atoms in Matlab. It was found that both proposed algorithm implementations 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dolezal, R., Ramalho, T., Franca, T.C., Kuca, K.: Parallel Flexible Molecular Docking in Computational Chemistry on High Performance Computing Clusters. In: Núñez, M., Nguyen. (eds.), LNCS, vol. 9330, pp. 418–427. Springer, Heidelberg (2015)
Bajorath, J.: Integration of virtual and high-throughput screening. Nat. Rev. Drug Discov. 1, 882–894 (2002)
Kubinyi, H.: Success stories of computer-aided design. In: Computer Applications in Pharmaceutical Research and Development, pp. 377–724. Wiley, New Jersey (2006)
Veselovsky, A.V., Ivanov, A.S.: Strategy of computer-aided drug design. Curr. Drug Targets Infect. Disord. 3, 33–40 (2003)
Taminau, J., Thijs, G., De Winter, H.: Pharao. J. Mol. Graph. Model. 27, 161–169 (2008)
Tosco, P., Balle, T., Shiri, F.: Open3DALIGN. J. Com. Aid. Mol. Des. 25, 777–783 (2011)
Taylor, W.R., May, A.C., Brown, N.P., Aszodi, A.: Protein structure: geometry, topology and classification. Reg. Prog. Phys. 64, 517–590 (2001)
Carbó, R., Leyda, L., Arnau, M.: How similar is a molecule to another? Int. J. Quant. Chem. 17, 1185–1189 (1980)
Sierk, M.L., Pearson, W.R.: Sensitivity and selectivity in protein structure comparison. Protein Sci. 13, 773–785 (2004)
McLachlan, A.: Rapid comparison of protein structures. Acta Cryst. 38A, 871–873 (1982)
Diamond, R.: A note on the rotational superposition problem. Acta Cryst. 44A, 211–216 (1998)
Kabsch, W.: A discussion of the solution for the best rotation to relate two sets of vectors. Acta Cryst. 34A, 827–828 (1978)
Ypma, T.: Historical development of the Newton-Raphson method. SIAM Rev. 37, 531–551 (1995)
Theobald, D.L.: Rapid calculation of RMSDs using a quaternion-based characteristic polynomial. Acta Cryst. 61A, 478–480 (2005)
Popov, P., Grudinin, S.: Rapid determination of RMSDs corresponding to macromolecular rigid body motions. J. Comput. Chem. 35, 950–956 (2014)
Acknowledgements
The work was supported by the Ministry of Education, Youth and Sports of Czech Republic (project ERDF no. CZ.02.1.01/0.0/0.0/18_069/0010054).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dolezal, R., Fronckova, K., Kirimtat, A., Krejcar, O. (2020). Computational Complexity of Kabsch and Quaternion Based Algorithms for Molecular Superimposition in Computational Chemistry. In: Iliadis, L., Angelov, P., Jayne, C., Pimenidis, E. (eds) Proceedings of the 21st EANN (Engineering Applications of Neural Networks) 2020 Conference. EANN 2020. Proceedings of the International Neural Networks Society, vol 2. Springer, Cham. https://doi.org/10.1007/978-3-030-48791-1_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-48791-1_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-48790-4
Online ISBN: 978-3-030-48791-1
eBook Packages: Computer ScienceComputer Science (R0)