A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems

Distance geometry is a branch of Mathematics which studies geometric relations having distances as primitive elements. Its fundamental problem, the distance geometry problem, consists in determining point positions in $$\mathbb {R}^K$$ R K such that their Euclidean distances match those in a given list of inter-point distances. Such problem can be cast as a global optimization problem which is often tackled with continuous optimization techniques. If $$K=3$$ K = 3 , it is called molecular DGP (MDGP). Under assumptions on the available distances in this list, the search space for the MDGP can be discretized so that it is able to be designed as a binary tree, giving birth to the discretized MDGP. The main method to solve it is the Branch-and-Prune Algorithm, a recursive and combinatorial tool that explores such tree in a depth-first search and whose classical formulation is based in a homogeneous matrix product that encodes one translation and two rotations. This paper presents a numerical study on the theoretical computational effort to do that task together with a quaternionic proposal as an alternative for the formulation of BP and the respective analogous numerical study, for comparing with the matrix one. Additionally, best-and-worst-case analyzes for both approaches are displayed. Finally, in order to validate the new formulation as having better computational performance for BP, a set of computational experiments are shown using artificial Lavor instances and pre-processed proteic examples which have been generated from structures withdrawn from the worldwide protein data bank.