Abstract
Given a weighted, undirected simple graph G = (V, E, d) (where \({d:E\to\mathbb{R}_+}\)), the distance geometry problem (DGP) is to determine an embedding \({x:V\to\mathbb{R}^K}\) such that \({\forall \{i,j\} \in E\;\|x_i-x_j\|=d_{ij}}\) . Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berman H., Westbrook J., Feng Z., Gilliland G., Bhat T., Weissig H., Shindyalov I., Bourne P.: The protein data bank. Nucleic Acid Res. 28, 235–242 (2000)
Blumenthal L.: Theory and applications of distance geometry. Oxford University Press, Oxford (1953)
Carvalho R., Lavor C., Protti F.: Extending the geometric build-up algorithm for the molecular distance geometry problem. Inf. Process. Lett. 108, 234–237 (2008)
Cook C., Kim D.: Best sorting algorithm for nearly sorted lists. Commun. ACM 23(11), 620–624 (1980)
Dong Q., Wu Z.: A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data. J. Global Optim. 26, 321–333 (2003)
Eren, T., Goldenberg, D., Whiteley, W., Yang, Y., Morse, A., Anderson, B., Belhumeur, P.: Rigidity, computation, and randomization in network localization. IEEE Infocom Proceedings pp. 2673–2684 (2004)
Fourer R., Gay D.: The AMPL book. Duxbury Press, Pacific Grove (2002)
Gu J., Du B., Pardalos P.: Multispace search for protein folding. In: Biegler, L., Coleman, T., Conn, A., Santosa, F. (eds) Large-scale optimization with applications, Part III: molecular structure and optimization, pp. 47–68. Springer, Berlin (1997)
Henneberg L.: Die graphische Statik der starren Systeme. B.G. Teubner, Leipzig (1911)
Huang H., Pardalos P.: A multivariate partition approach to optimization problems. Cyber. Syst. Anal. 38, 265–275 (2002)
Huang H.X., Liang Z.A., Pardalos P.: Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems. J. Global Optim. 25, 3–21 (2003)
ILOG: ILOG CPLEX 11.0 User’s Manual. ILOG S.A., Gentilly, France (2008)
Jiao, Y., Stillinger, F., Torquato, S.: Geometrical ambiguity of pair statistics I. point configurations. Tech. Rep. 0908.1366v1, arXiv (2009)
Lavor C., Liberti L., Maculan N.: Computational experience with the molecular distance geometry problem. In: Pintér, J. (eds) Global optimization: scientific and engineering case studies., pp. 213–225. Springer, Berlin (2006)
Lavor, C., Liberti, L., Maculan, N.: The discretizable molecular distance geometry problem. Tech. Rep. q-bio/0608012, arXiv (2006)
Lavor C., Liberti L., Maculan N.: Molecular distance geometry problem. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of optimization, second edn., pp. 2305–2311. Springer, New York (2009)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. (accepted)
Lavor, C., Liberti, L., Mucherino, A., Maculan, N.: On a discretizable subclass of instances of the molecular distance geometry problem. In: Shin, D. (ed.) Proceedings of the 24th Annual ACM Symposium on Applied Computing, pp. 804–805. ACM (2009)
Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: Computing artificial backbones of hydrogen atoms in order to discover protein backbones. In: Proceedings of the International Multiconference on Computer Science and Information Technology, pp. 751–756. IEEE, Mragowo, Poland (2009)
Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: On the computation of protein backbones by using artificial backbones of hydrogens. J. Global Optim. (accepted). doi:10.1007/s10898-010-9584-y
Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: On the solution of molecular distance geometry problems with interval data. In: Proceedings of the International Workshop on Computational Proteomics. IEEE, Hong Kong (2010)
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., Masson, B., Lavor, C., Lee, J., Mucherino, A.: On the number of solutions of the discretizable molecular distance geometry problem. Tech. Rep. 1010.1834v1[cs.DM], arXiv (2010)
Moré J., Wu Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7(3), 814–846 (1997)
Mucherino, A., Lavor, C.: The branch and prune algorithm for the molecular distance geometry problem with inexact distances. In: Proceedings of the International Conference on Computational Biology, vol. 58, pp. 349–353. World Academy of Science, Engineering and Technology (2009)
Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. (in revision)
Mucherino A., Lavor C., Liberti L., Maculan N.: On the definition of artificial backbones for the discretizable molecular distance geometry problem. Mathematica Balkanica 23, 289–302 (2009)
Mucherino, A., Lavor, C., Maculan, N.: The molecular distance geometry problem applied to protein conformations. In: Cafieri, S., Mucherino, A., Nannicini, G., Tarissan, F., Liberti, L. (eds.) Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 337–340. École Polytechnique, Paris (2009)
Mucherino, A., Liberti, L., Lavor, C., Maculan, N.: Comparisons between an exact and a metaheuristic algorithm for the molecular distance geometry problem. In: Rothlauf, F. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference, pp. 333–340. ACM, Montreal (2009)
Pardalos P., Liu X.: A tabu based pattern search method for the distance geometry problem. In: Giannessi, F., Rapcsák, T., Komlósi, S. (eds) (eds.) New trends in mathematical programming, Kluwer, Dordrecht (1998)
Pardalos, P., Shalloway, D., Xue, G. (eds.) (1996) Global minimization of nonconvex energy functions: molecular conformation and protein folding, vol. 23. Am. Math. Soc.
Schank T., Wagner D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: Nikoletseas, S. (eds) Workshop on Experimental Algorithms, LNCS, vol. 3503, pp. 606–609. Springer, Berlin (2005)
So M.C., Ye Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)
Wu D., Wu Z.: An updated geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data. J. Global Optim. 37, 661–673 (2007)
Wu D., Wu Z., Yuan Y.: Rigid versus unique determination of protein structures with geometric buildup. Optim. Lett. 2(3), 319–331 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lavor, C., Lee, J., Lee-St. John, A. et al. Discretization orders for distance geometry problems. Optim Lett 6, 783–796 (2012). https://doi.org/10.1007/s11590-011-0302-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0302-6