Abstract
The problem of 3D protein structure determination using distance information from nuclear magnetic resonance (NMR) experiments is a classical problem in distance geometry. NMR data and the chemistry of proteins provide a way to define a protein backbone order such that the distances related to the pairs of atoms \(\{i-3,i\},\{i-2,i\},\{i-1,i\}\) are available, implying a combinatorial method to solve the problem, called branch-and-prune (BP). There are two main steps in BP algorithm: the first one (the branching phase) is to intersect three spheres centered at the positions for atoms \( i-3,i-2,i\), with radius given by the atomic distances \( d_{i-3,i},d_{i-2,i},d_{i-1,i}\), respectively, to obtain two possible positions for atom i; and the second one (the pruning phase) is to check if additional spheres (related to distances \(d_{j,i}\), \(j<i-3\)) can be used to select one of the two possibilities for atom i. Differently from distances \(d_{i-2,i},d_{i-1,i}\) (associated to bond lenghts and bond angles), distances \(d_{j,i}\), \(j\le i-3\), may not be precise. BP algorithm has difficulties to deal with uncertainties, and this paper proposes the oriented conformal geometric algebra to take care of intersection of spheres when their centers and radius are not precise.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agra, A., Figueiredo, R., Lavor, C., Maculan, N., Pereira, A., Requejo, C.: Feasibility check for the distance geometry problem: an application to molecular conformations. Int. Trans. Oper. Res. 24, 1023–1040 (2017)
Alves, R., Lavor, C.: Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem. Adv. Appl. Clifford Algebra 27, 439–452 (2017)
Alves, R., Lavor, C., Souza, C., Souza, M.: Clifford algebra and discretizable distance geometry. Math. Methods Appl. Sci. 41, 3999–4346 (2018)
Billinge, S., Duxbury, P., Gonçalves, D., Lavor, C., Mucherino, A.: Assigned and unassigned distance geometry: applications to biological molecules and nanostructures. 4OR 14, 337–376 (2016)
Billinge, S., Duxbury, P., Gonçalves, D., Lavor, C., Mucherino, A.: Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures. Ann. Oper. Res. 271, 161–203 (2018)
Cameron, J., Lasenby, J.: Oriented conformal geometric algebra. Adv. Appl. Clifford Algebra 18, 523–538 (2008)
Cassioli, A., Gunluk, O., Lavor, C., Liberti, L.: Discretization vertex orders in distance geometry. Discrete Appl. Math. 197, 27–41 (2015)
Cassioli, A., Bordeaux, B., Bouvier, G., Mucherino, A., Alves, R., Liberti, L., Nilges, M., Lavor, C., Malliavin, T.: An algorithm to enumerate all possible protein conformations verifying a set of distance constraints. BMC Bioinform. 16, 16–23 (2015)
Costa, T., Bouwmeester, H., Lodwick, W., Lavor, C.: Calculating the possible conformations arising from uncertainty in the molecular distance geometry problem using constraint interval analysis. Inform. Sci. 415–416, 41–52 (2017)
Crippen, G., Havel, T.: Distance Geometry and Molecular Conformation. Wiley, New York (1988)
Donald, B.: Algorithms in Structural Molecular Biology. MIT Press, Cambridge (2011)
Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Morgan Kaufman, San Mateo (2007)
Dress, A., Havel, T.: Distance geometry and geometric algebra. Found. Phys. 23, 1357–1374 (1993)
Fidalgo, F., Gonalves, D., Lavor, C., Liberti, L., Mucherino, A.: A symmetry-based splitting strategy for discretizable distance geometry problems. J. Glob. Optim. 71, 717–733 (2018)
Gonçalves, D., Mucherino, A.: Discretization orders and efficient computation of Cartesian coordinates for distance geometry. Optim. Lett. 8, 2111–2125 (2014)
Gonçalves, D., Mucherino, A., Lavor, C., Liberti, L.: Recent advances on the interval distance geometry problem. J. Glob. Optim. 69, 525–545 (2017)
Hestenes, D.: Old wine in new bottles: a new algebraic framework for computational geometry. In: Corrochano E. B., Sobczyk G. (eds.) Geometric Algebra with Applications in Science and Engineering. Birkhäuser, Boston (2001)
Hildenbrand, D.: Foundations of Geometric Algebra Computing. Springer, Berlin Heidelberg (2012)
Lavor, C., Xambó-Descamps, S., Zaplana, I.: A Geometric Algebra Invitation to Space-Time Physics Robotics and Molecular Geometry. SpringerBriefs in Mathematics. Springer, Berlin Heidelberg (2018)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: Recent advances on the discretizable molecular distance geometry problem. Eur. J. Oper. Res. 219, 698–706 (2012)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52, 115–146 (2012)
Lavor, C., Liberti, L., Mucherino, A.: The interval BP algorithm for the discretizable molecular distance geometry problem with interval data. J. Glob. Optim. 56, 855–871 (2013)
Lavor, C., Alves, R., Figueiredo, W., Petraglia, A., Maculan, N.: Clifford algebra and the discretizable molecular distance geometry problem. Adv. Appl. Clifford Algebra 25, 925–942 (2015)
Lavor, C., Liberti, L., Lodwick, W., Mendonça da Costa, T.: An Introduction to Distance Geometry applied to Molecular Geometry. SpringerBriefs in Computer Science. Springer, Berlin Heidelberg (2017)
Lavor, C., Liberti, L., Donald, B., Worley, B., Bardiaux, B., Malliavin, T., Nilges, M.: Minimal NMR distance information for rigidity of protein graphs. Discrete Applied Mathematics (2018) (to appear)
Li, H., Hestenes, D., Rockwood, A.: Generalized Homogeneous Coordinates for Computational Geometry. In: Sommer, G. (ed.) Geometric Computing with Clifford Algebra, pp. 25–58. Springer, Berlin Heidelberg (2001)
Liberti, L., Lavor, C.: Open Research Areas in Distance Geometry. In: Pardalos, P., Migdalas, A. (eds.) Open Problems in Optimization and Data Analysis. Springer, Berlin Heidelberg (2018). (to appear)
Liberti, L., Lavor, C., Maculan, N.: A branch-and-prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15, 1–17 (2008)
Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18, 33–51 (2010)
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56, 3–69 (2014)
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)
Liberti, L., Lavor, C.: Six mathematical gems from the history of distance geometry. Int. Trans. Oper. Res. 23, 897–920 (2016)
Liberti, L., Lavor, C.: Euclidean Distance Geometry. An Introduction. Springer, Berlin (2017)
Menger, K.: Untersuchungen uber allgemeine Metrik. Math. Ann. 100, 75–163 (1928)
Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6, 1671–1686 (2012)
Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.): Distance Geometry: Theory, Methods, and Applications. Springer, Berlin (2013)
Souza, M., Lavor, C., Muritiba, A., Maculan, N.: Solving the molecular distance geometry problem with inaccurate distance data. BMC Bioinform. 14, S71–S76 (2013)
Stolfi, J.: Oriented Projective Geometry—A Framework for Geometric Computations. Academic Press, Cambridge (1991)
Worley, B., Delhommel, F., Cordier, F., Malliavin, T., Bardiaux, B., Wolff, N., Nilges, M., Lavor, C., Liberti, L.: Tuning interval branch-and-prune for protein structure determination. J. Glob. Optim. 72, 109–127 (2018)
Wütrich, K.: Protein structure determination in solution by nuclear magnetic resonance spectroscopy. Science 243, 45–50 (1989)
Acknowledgements
We would like to thank the Brazilian research agencies CNPq, CAPES, and FAPESP, for their financial support, and also Leo Dorst, for his comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article is part of the Topical Collection on Homage to Prof. W.A. Rodrigues Jr edited by Jayme Vaz Jr.
Rights and permissions
About this article
Cite this article
Lavor, C., Alves, R. Oriented Conformal Geometric Algebra and the Molecular Distance Geometry Problem. Adv. Appl. Clifford Algebras 29, 9 (2019). https://doi.org/10.1007/s00006-018-0925-0
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00006-018-0925-0