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

Felipe Fidalgo (), Emerson Castelani () and Guilherme Philippi ()
Additional contact information
Felipe Fidalgo: Universidade Federal de Santa Catarina
Emerson Castelani: Universidade Estadual de Maringá
Guilherme Philippi: Universidade Federal de Santa Catarina

Computational Optimization and Applications, 2024, vol. 87, issue 2, No 7, 530 pages

Abstract: Abstract 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.

Keywords: Distance geometry; Quaternions; Branch-and-prune; Numerical optimization; Protein conformation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-023-00526-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00526-8

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-023-00526-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().