Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

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

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

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\) 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\), 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Data availability

All the data and the scripts which are involved in the present work can be found in https://github.com/evcastelani/MolecularConformation.jl. Any other information can be provided by the authors upon request.

Notes

  1. https://github.com/evcastelani/MolecularConformation.jl.

  2. https://github.com/caomem/PDBReader.

  3. https://github.com/caomem/PDBFileCreator.

  4. https://github.com/JuliaCI/BenchmarkTools.jl

  5. The full table of artificial results can be obtained in https://bit.ly/COAPArtificialResults

  6. The full list of tests in pre-processed proteic instances including all complete version tables expressed in this article are available at https://bit.ly/COAPRealResults.

References

  1. Liberti, L., Lavor, C.: Six mathematical gems from the history of distance geometry. Int. Trans. Oper. Res. 23, 897–920 (2016)

    Article  MathSciNet  Google Scholar 

  2. Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3–69 (2014)

    Article  MathSciNet  Google Scholar 

  3. Moré, J., Wu, Z.: Global continuation for distance geometry problems. SIAM J. Comput. 7(3), 814–836 (1997)

    MathSciNet  Google Scholar 

  4. Hoai An, L.T.: Solving large scale molecular distance geometry problems by a smoothing technique via the gaussian transform and dc programming. J. Glob. Optim. 27, 375–397 (2003)

    Article  Google Scholar 

  5. Hoai An, L.T., Tao, P.D.: Large scale molecular optimization from distance matrices by a DC optimization approach. SIAM J. Optim. 14, 77–114 (2003)

    Article  MathSciNet  Google Scholar 

  6. Biswas, P., Toh, K.C., Ye, Y.: A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput. 30(3), 1251–1277 (2008)

    Article  MathSciNet  Google Scholar 

  7. Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20(5), 2679–2708 (2010)

    Article  MathSciNet  Google Scholar 

  8. Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18(1), 33–51 (2011)

    Article  MathSciNet  Google Scholar 

  9. Liberti, L., Lavor, C.: Euclidean Distance Geometry: An Introduction. Springer Undergraduate Texts in Mathematics and Technology, Springer, New York (2017)

    Book  Google Scholar 

  10. Liberti, L.: Distance geometry and data science. TOP 28, 271–339 (2020)

    Article  MathSciNet  Google Scholar 

  11. Crippen, G., Havel, T.: Distance Geometry and Molecular Conformation. Research Studies Press, Taunton (1988)

    Google Scholar 

  12. Lavor, C., Liberti, L., Donald, B., Worley, B., Bardiaux, B., Malliavin, T.E., Nilges, M.: Minimal NMR distance information for rigidity protein graphs. Discrete Appl. Math. 256, 91–104 (2019)

    Article  MathSciNet  PubMed  Google Scholar 

  13. Gonçalves, D.S.: A least-squares approach for discretizable distance geometry problems with inexact distances. Optim. Lett. 14, 423–437 (2019)

    Article  MathSciNet  Google Scholar 

  14. Lavor, C., Liberti, L., Mucherino, A.: The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances. J. Glob. Optim. 56, 855–871 (2013)

    Article  MathSciNet  Google Scholar 

  15. Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52, 115–146 (2012)

    Article  MathSciNet  Google Scholar 

  16. Henneberg, L.: Die Graphische Statik Der Starren Systeme. Nabu Press, Charleston (1886)

    Google Scholar 

  17. Liberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A.: On the number of realizations of certain Henneberg graphs arising in protein conformation. Discrete Appl. Math. 165, 213–232 (2014)

    Article  MathSciNet  Google Scholar 

  18. Mucherino, A., Lavor, C., Liberti, L.: Exploiting symmetry properties of the discretizable molecular distance geometry problem. J. Bioinform. Comput. Biol. 10(3), 1–15 (2012)

    Article  Google Scholar 

  19. Pogorelov, A.: Geometry. MIR Publishers, Moscow (1987)

    Google Scholar 

  20. Golub, G., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, Baltimore (1996)

    Google Scholar 

  21. Beutelspacher, A., Rosenbaum, U.: Projective Geometry: From Foundations to Applications. Cambridge University Press, Cambridge (1998)

    Google Scholar 

  22. Clifford, W.K.: Preliminary sketch of biquaternions. Proc. Lond. Math. Soc. 1, 381–395 (1871)

    Article  MathSciNet  Google Scholar 

  23. Kuipers, J.B.: Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality. Princeton University Press, Princeton (2002)

    Google Scholar 

  24. Hamilton, W.R.: Elements of Quaternions, vol. 1. Green and Co., Longmans (1899)

    Google Scholar 

  25. Fog, A.: Instruction tables: lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs. https://www.agner.org/optimize/instruction_tables.pdf. Accessed 15 Aug 2019

  26. Dong, Q., Wu, Z.: A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. J. Glob. Optim. 22, 365–375 (2002)

    Article  MathSciNet  Google Scholar 

  27. Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017)

    Article  MathSciNet  Google Scholar 

  28. Mucherino, A., Liberti, L., Lavor, C.: Md-jeep: an implementation of a branch and prune algorithm for distance geometry problems. In: International Congress on Mathematical Software, ICMS. Lecture Notes on Computer Science, vol. 6327, pp. 186–197. Springer, Kobe (2010)

  29. Lavor, C.: On generating instances for the molecular distance geometry problem. In: Liberti, L., Maculan, N. (eds.) Global Optimization: From Theory to Implementation, pp. 405–414. Springer, New York (2006)

    Chapter  Google Scholar 

  30. Berman, H.M., Hendrick, K., Nakamura, H.: Announcing the worldwide protein data bank. Nat. Struct. Mol. Biol. 10, 980 (2003)

    Article  CAS  Google Scholar 

  31. Creighton, T.: Proteins: Structures and Molecular Properties, 2nd edn. W. H. Freeman, New York (1993)

    Google Scholar 

  32. Nelson, D.L., Cox, M.M.: Lehninger Principles of Biochemistry, 6th edn. W. H. Freeman, New York (2004)

    Google Scholar 

  33. Liberti, L., Lavor, C., Maculan, N.: A branch-and-prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15(1), 1–17 (2008)

    Article  MathSciNet  Google Scholar 

  34. Panda, P.R., Catthoor, F., Dutt, N.D., Danckaert, K., Brockmeyer, E., Kulkarni, C., Vandercappelle, A., Kjeldsberg, P.G.: Data and memory optimization techniques for embedded systems. ACM Trans. Des. Autom. Electron. Syst. (TODAES) 6(2), 149–206 (2001)

    Article  Google Scholar 

  35. Benchmarking optimization software with performance profiles: Dolan, E., Morè. J. Math. Program. 91, 201–213 (2002)

    Google Scholar 

Download references

Acknowledgements

First of all, the authors would like to thank the reviewers for all the valuable suggestions that made this manuscript even better. The authors would also like to thank Leandro A. F. Fernandes, Bruce R. Donald, Lidiane Meier and Carlile Lavor for the important discussions.

Funding

GP would like to thank CNPq (Brazilian Research Funding Agency) for financial support. FF thanks UFSC, CAPES (Brazilian Council for Improvement of Higher Level Personnel) and CNPq for funding. EVC thanks UEM for all the support.

Author information

Authors and Affiliations

  1. Department of Mathematics, Universidade Federal de Santa Catarina, 2514 João Pessoa street, Velha, Blumenau, Santa Catarina, 89036004, Brazil

    Felipe Fidalgo & Guilherme Philippi

  2. Department of Mathematics, Universidade Estadual de Maringá, 5790 Colombo Avenue, Jardim Universitário, Maringá, Paraná, 87020900, Brazil

    Emerson Castelani

Authors
  1. Felipe Fidalgo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Emerson Castelani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guilherme Philippi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Felipe Fidalgo.

Ethics declarations

Conflict of interest

The authors would like to declare that there are no conflict of interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fidalgo, F., Castelani, E. & Philippi, G. A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems. Comput Optim Appl 87, 501–530 (2024). https://doi.org/10.1007/s10589-023-00526-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-023-00526-8

Keywords

Search

Navigation