Abstract
Nuclear Magnetic Resonance experiments can provide distances between pairs of atoms of a protein that are close enough and the problem is how to determine the 3D protein structure based on this partial distance information, called Molecular Distance Geometry Problem. It is possible to define an atomic order 1, ..., n and solve the problem iteratively using an exact method, called Branch-and-Prune (BP). The main step of BP algorithm is to solve a quadratic system to get the two possible positions for i, i > 3, in terms of the positions of i−3, i−2, i−1 and the distances d i−1, i , d i−2, i , d i−3, i . Because of uncertainty in NMR data, some of the distances d i−3, i may not be precise and the main problem to apply BP is related to the difficulty of obtaining an analytical expression of the position of atom i in terms of the positions of the three previous ones and the corresponding distances. We present such expression and although it is similar to one already existing in the literature, based on polyspherical coordinates, a new proof is given, based on Clifford algebra, and we also explain how such expression can be useful in BP using a parameterization which depends on d i−3, i . The results suggest that a master equation might exist, what is generally not believed by many researchers.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alves R., Lavor C.: Clifford algebra applied to Grover’s algorithm. Advances in Applied Clifford Algebra 20, 477–488 (2010)
Berger B., Kleinberg J., Leighton T.: Reconstructing a three-dimensional model with arbitrary errors. Journal of the ACM 46, 212–235 (1999)
Brünger A., Nilges M.: Computational challenges for macromolecular structure determination by X-ray crystallography and solution NMR-spectroscopy. Quarterly Reviews of Biophysics 26, 49–125 (1993)
A. Cassioli, O. Gunluk, C. Lavor, and L. Liberti, Discretization vertex orders in distance geometry. IBM Research Report RC25434, 2013 (accepted in Discrete Applied Mathematics).
P. Chys, Application of geometric algebra for the description of polymer conformations. Journal of Chemical Physics 128 (2008), 104107(1)-104107(12).
Chys P., Chacón P.: Spinor product computations for protein conformations. Journal of Computational Chemistry 33, 1717–1729 (2012)
Costa V., Mucherino A., Lavor C., Cassioli A., Carvalho L., Maculan N.: Discretization orders for protein side chains. Journal of Global Optimization 60, 333–349 (2014)
G. Crippen and T. Havel, Distance Geometry and Molecular Conformation. Wiley, New York, 1988.
T. Eren, D. Goldenberg, W. Whiteley, Y. Yang, A. Morse, B. Anderson, and P. Belhumeur, Rigidity, computation, and randomization in network localization. IEEE Infocom Proc. 4 (2004), pp. 2673–2684.
D. Gonçalves and A. Mucherino, Discretization orders and efficient computation of Cartesian coordinates for distance geometry. Optimization Letters, 8 (2014), 2111-2125.
F. Harary, Graph Theory. Addison-Wesley, Reading, 1994.
T. Havel, Distance geometry. In D. Grant and R. Harris, (eds.). Encyclopedia of Nuclear Magnetic Resonance,, Wiley, New York (1995) pp. 1701-1710.
D. Hestenes, New Foundations for Classical Mechanics. Kluwer, Boston, 1999.
Lavor C., Maculan N.: A function to test methods applied to global minimization of potential energy of molecules. Numerical Algorithms 35, 287–300 (2004)
C. Lavor, L. Liberti, and N. Maculan, Computational experience with the molecular distance geometry problem. In Global Optimization: Scientific and Engineering Case Studies, J. Pintér, ed., Springer, Berlin (2006), pp. 213–225.
Lavor C.: Analytic evaluation of the gradient and Hessian of molecular potential energy functions. Physica D 227, 135–141 (2007)
Lavor C., Liberti L., Maculan N., Mucherino A.: Recent advances on the discretizable molecular distance geometry problem. European Journal of Operational Research 219, 698–706 (2012)
Lavor C., Liberti L., Maculan N., Mucherino A.: The discretizable molecular distance geometry problem. Computational Optimization and Applications 52, 115–146 (2012)
Lavor C., Liberti L., Mucherino A.: The interval BP algorithm for the discretizable molecular distance geometry problem with interval data. Journal of Global Optimization 56, 855–871 (2013)
Liberti L., Lavor C., Maculan N.: A branch-and-prune algorithm for the molecular distance geometry problem. International Transactions in Operational Research 15, 1–17 (2008)
Liberti L., Lavor C., Mucherino A., Maculan N.: Molecular distance geometry methods: from continuous to discrete. International Transactions in Operational Research 18, 33–51 (2010)
Liberti L., Lavor C., Maculan N., Mucherino A.: Euclidean distance geometry and applications. SIAM Review 56, 3–69 (2014)
P. Lounesto, Clifford Algebras and Spinnors. Cambridge University Press, Cambridge, 1997.
N. Melo and C. Lavor, A Clifford algebra of signature (n,3n) and the density operators of quantum information theory. Advances in Applied Clifford Algebra 23 (2013), 143-152.
Mucherino A., Lavor C., Liberti L.: The discretizable distance geometry problem. Optimization Letters 6, 1671–1686 (2012)
A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, eds., Distance Geometry: Theory, Methods, and Applications. Springer, New York, 2013.
Neumaier A.: Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Review 39, 407–460 (1997)
Pesonen J., Henriksson O.: Polymer conformations in internal (polyspherical) coordinates. Journal of Computational Chemistry 31, 1874–1881 (2009)
A. Pogorelov, Geometry. Mir Publishers, Moscow, 1987.
Seok C., Coutsias E.: Efficiency of rotational operators for geometric manipulation of chain molecules. Bulletin of the Korean Chemical Society 28, 1705–1708 (2007)
M. Souza, A. Xavier, C. Lavor, and N. Maculan, Hyperbolic smoothing and penalty techniques applied to molecular structure determination. Operations Research Letters 39 (2011), 461–465.
M. Souza, C. Lavor, A. Muritiba, and N. Maculan, Solving the molecular distance geometry problem with inaccurate distance data. BMC Bioinformatics 14 (2013), S71-S76.
Wütrich K.: Protein structure determination in solution by nuclear magnetic resonance spectroscopy. Science 243, 45–50 (1989)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lavor, C., Alves, R., Figueiredo, W. et al. Clifford Algebra and the Discretizable Molecular Distance Geometry Problem. Adv. Appl. Clifford Algebras 25, 925–942 (2015). https://doi.org/10.1007/s00006-015-0532-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00006-015-0532-2