The discretizable molecular distance geometry problem. (English) Zbl 1259.90153
Summary: Given a simple weighted undirected graph \(G=(V,E,d)\) with \(d:E\rightarrow \mathbb R_+\), the Molecular distance geometry problem (MDGP) consists in finding an embedding \(x:V\rightarrow \mathbb R^3\) such that \(\| x_u-x_v\| =d_{uv}\) for each \(\{u,v\}\in E\). We show that under a few assumptions usually satisfied in proteins, the MDGP can be formulated as a search in a discrete space. We call this MDGP subclass the Discretizable MDGP (DMDGP). We show that the DMDGP is NP-hard and we propose a solution algorithm called branch-and-prune (BP). The BP algorithm performs remarkably well in practice in terms of speed and solution accuracy, and can be easily modified to find all incongruent solutions to a given DMDGP instance. We show computational results on several artificial and real-life instances.
MSC:
| 90C35 | Programming involving graphs or networks |
References:
| [1] | An, L.T.H.: Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and d.c. programming. J. Glob. Optim. 27, 375–397 (2003) · Zbl 1064.90036 · doi:10.1023/A:1026016804633 |
| [2] | An, L.T.H., Tao, P.D.: Large-scale molecular optimization from distance matrices by a d.c. optimization approach. SIAM J. Optim. 14, 77–114 (2003) · Zbl 1075.90071 · doi:10.1137/S1052623498342794 |
| [3] | Bachrach, J., Taylor, C.: Localization in sensor networks. In: Stojmenović, I. (ed.) Handbook of Sensor Networks, pp. 3627–3643. Wiley, New York (2005) |
| [4] | Barker, G.: The lattice of faces of a finite dimensional cone. Linear Algebra Appl. 7(1), 71–82 (1973) · Zbl 0249.15010 · doi:10.1016/0024-3795(73)90038-4 |
| [5] | Berger, B., Kleinberg, J., Leighton, T.: Reconstructing a three-dimensional model with arbitrary errors. J. ACM 46(2), 212–235 (1999) · Zbl 1065.68574 · doi:10.1145/301970.301972 |
| [6] | Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H., Shindyalov, I.N., Bourne, P.E.: The protein data bank. Nucleic Acids Res. 28, 235–242 (2000) · doi:10.1093/nar/28.1.235 |
| [7] | Biswas, P.: Semidefinite programming approaches to distance geometry problems. Ph.D. thesis, Stanford University (2007) |
| [8] | Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN04), New York, NY, USA, pp. 46–54. ACM, New York (2004) |
| [9] | Biswas, P., Ye, Y.: A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. In: Multiscale Optimization Methods and Applications, vol. 82, pp. 69–84. Springer, Berlin (2006) · Zbl 1100.90029 |
| [10] | Biswas, P., Lian, T., Wang, T., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sens. Networks 2, 188–220 (2006) · doi:10.1145/1149283.1149286 |
| [11] | Biswas, P., Liang, T.-C., Toh, K.-C., Wang, T.-C., Ye, Y.: Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Trans. Autom. Sci. Eng. 3, 360–371 (2006) · doi:10.1109/TASE.2006.877401 |
| [12] | 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) · Zbl 1161.49028 · doi:10.1137/05062754X |
| [13] | Blumenthal, L.: Theory and Applications of Distance Geometry. Oxford University Press, London (1953) · Zbl 0050.38502 |
| [14] | Burkowski, F.: Structural Bioinformatics: An Algorithmic Approach. CRC Press, Boca Raton (2009) · Zbl 1259.92029 |
| [15] | Carvalho, R.S., Lavor, C., Protti, F.: Extending the geometric build-up algorithm for the molecular distance geometry problem. Inf. Process. Lett. 108, 234–237 (2008) · Zbl 1191.68772 · doi:10.1016/j.ipl.2008.05.009 |
| [16] | Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33, 549–563 (2005) · Zbl 1072.52016 · doi:10.1007/s00454-004-1124-4 |
| [17] | Creighton, T.: Proteins: Structures and Molecular Properties. Freeman, New York (1993) |
| [18] | Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation. Wiley, New York (1988) · Zbl 1066.51500 |
| [19] | Dattorro, J.: Convex Optimization and Euclidean Distance Geometry. Annual Reviews, Palo Alto (2005) · Zbl 1142.15014 |
| [20] | 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) · Zbl 1045.90093 · doi:10.1023/A:1013857218127 |
| [21] | Dong, Q., Wu, Z.: A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data. J. Glob. Optim. 26, 321–333 (2003) · Zbl 1032.92036 · doi:10.1023/A:1023221624213 |
| [22] | Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Morse, A.S., Anderson, B.D.O., Belhumeur, P.N.: Rigidity, computation, and randomization in network localization. In: IEEE Infocom Proceedings, pp. 2673–2684 (2004) |
| [23] | Floyd, R.W.: Algorithm 97: Shortest path. Commun. ACM 5(6), 345 (1962) · doi:10.1145/367766.368168 |
| [24] | Glunt, W., Hayden, T.H., Hong, S., Wells, J.: An alternating projection algorithm for computing the nearest Euclidean distance matrix. SIAM J. Matrix Anal. Appl. 11(4), 589–600 (1990) · Zbl 0728.65034 · doi:10.1137/0611042 |
| [25] | Grosso, A., Locatelli, M., Schoen, F.: Solving molecular distance geometry problems by global optimization algorithms. Comput. Optim. Appl. 43, 23–27 (2009) · Zbl 1176.90567 · doi:10.1007/s10589-007-9127-8 |
| [26] | Havel, T.: Distance geometry. In: Grant, D., Harris, R. (eds.) Encyclopedia of Nuclear Magnetic Resonance, pp. 1701–1710. Wiley, New York (1995) |
| [27] | Hendrickson, B.A.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5, 835–857 (1995) · Zbl 0844.05093 · doi:10.1137/0805040 |
| [28] | Huang, H.-X., Liang, Z.-A., Pardalos, P.: Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems. J. Glob. Optim. 25, 3–21 (2003) · Zbl 1037.15015 · doi:10.1023/A:1021336413386 |
| [29] | Johnson, C., Kroschel, B., Wolkowicz, H.: An interior-point method for approximate positive semidefinite completions. Comput. Optim. Appl. 9, 175–190 (1998) · Zbl 0907.90207 · doi:10.1023/A:1018363021404 |
| [30] | Kearsley, A., Tapia, R., Trosset, M.: The solution of the metric stress and stress problems in multidimensional scaling by newton’s method. Comput. Stat. 13, 369–396 (1998) · Zbl 0926.92002 |
| [31] | Krislock, N.: Semidefinite facial reduction for low-rank Euclidean distance matrix completion. Ph.D. thesis, University of Waterloo (2010) · Zbl 1229.90250 |
| [32] | Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20, 2679–2708 (2010) · Zbl 1229.90250 · doi:10.1137/090759392 |
| [33] | Laurent, M.: Matrix completion problems. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, 2nd edn., pp. 1967–1975. Springer, New York (2009) |
| [34] | 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, Berlin (2006) · Zbl 1100.90034 |
| [35] | Lavor, C., Liberti, L., Maculan, N.: Grover’s algorithm applied to the molecular distance geometry problem. In: Proc. of VII Brazilian Congress of Neural Networks, Natal, Brazil (2005) · Zbl 1136.92037 |
| [36] | Lavor, C., Liberti, L., Maculan, N.: Computational experience with the molecular distance geometry problem. In: Pintér, J. (ed.) Global Optimization: Scientific and Engineering Case Studies, pp. 213–225. Springer, Berlin (2006) · Zbl 1129.90389 |
| [37] | Lavor, C., Liberti, L., Maculan, N.: The discretizable molecular distance geometry problem. Technical Report, arXiv: q-bio/0608012 (2006) · Zbl 1129.90389 |
| [38] | Lavor, C., Liberti, L., Maculan, N.: Molecular distance geometry problem. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, 2nd edn., pp. 2305–2311. Springer, New York (2009) |
| [39] | 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, New York (2009) · Zbl 1190.92009 |
| [40] | 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, Mragowo, Poland, pp. 751–756. IEEE Press, New York (2009) |
| [41] | 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, Hong Kong. IEEE Press, New York (2010) · Zbl 1253.05132 |
| [42] | Lavor, C., Lee, J., Lee-St. John, A., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. (accepted for publication) · Zbl 1258.90096 |
| [43] | Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: On the computation of protein backbones by using artificial backbones of hydrogens. J. Glob. Optim. (accepted). doi: 10.1007/s10898-010-9584-y · Zbl 1219.90209 |
| [44] | Liberti, L., Lavor, C., Maculan, N.: Double VNS for the molecular distance geometry problem. In: Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005) · Zbl 1129.90389 |
| [45] | 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) · Zbl 1136.92037 · doi:10.1111/j.1475-3995.2007.00622.x |
| [46] | Liberti, L., Lavor, C., Maculan, N., Marinelli, F.: Double variable neighbourhood search with smoothing for the molecular distance geometry problem. J. Glob. Optim. 43, 207–218 (2009) · Zbl 1169.90470 · doi:10.1007/s10898-007-9218-1 |
| [47] | Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18, 33–51 (2010) · Zbl 1219.90177 · doi:10.1111/j.1475-3995.2009.00757.x |
| [48] | Liberti, L., Masson, B., Lavor, C., Lee, J., Mucherino, A.: On the number of solutions of the discretizable molecular distance geometry problem. Technical Report, arXiv: 1010.1834v1 [cs.DM] (2010) · Zbl 1342.90168 |
| [49] | Moré, J.J., Wu, Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7(3), 814–846 (1997) · Zbl 0891.90168 · doi:10.1137/S1052623495283024 |
| [50] | Moré, J.J., Wu, Z.: Distance geometry optimization for protein structures. J. Glob. Optim. 15, 219–234 (1999) · Zbl 0944.92012 · doi:10.1023/A:1008380219900 |
| [51] | 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. World Academy of Science, Engineering and Technology, vol. 58, pp. 349–353 (2009) · Zbl 1272.90074 |
| [52] | 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) |
| [53] | Mucherino, A., Lavor, C., Liberti, L., Talbi, E.-G.: A parallel version of the branch & prune algorithm for the molecular distance geometry problem. In: ACS/IEEE International Conference on Computer Systems and Applications (AICCSA10), Hammamet, Tunisia. IEEE Press, New York (2010) · Zbl 1294.68144 |
| [54] | 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, Montreal, pp. 333–340. ACM, New York (2009) · Zbl 1190.92009 |
| [55] | Mucherino, A., Liberti, L., Lavor, C.: MD-jeep: an implementation of a branch-and-prune algorithm for distance geometry problems. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) Mathematical Software. LNCS, vol. 6327, pp. 186–197. Springer, New York (2010) · Zbl 1294.68144 |
| [56] | Phillips, A.T., Rosen, J.B., Walke, V.H.: Molecular structure determination by convex underestimation of local energy minima. In: Pardalos, P.M., Shalloway, D., Xue, G. (eds.) Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding, vol. 23, pp. 181–198. American Mathematical Society, Providence (1996) · Zbl 0848.65048 |
| [57] | Pogorelov, A.: Geometry. Mir, Moscow (1987) |
| [58] | Roth, B.: Rigid and flexible frameworks. Am. Math. Mon. 88(1), 6–21 (1981) · Zbl 0455.51012 · doi:10.2307/2320705 |
| [59] | Santana, R., Larrañaga, P., Lozano, J.A.: Combining variable neighbourhood search and estimation of distribution algorithms in the protein side chain placement problem. In: Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005) · Zbl 1211.90316 |
| [60] | Santana, R., Larra naga, P., Lozano, J.A.: Side chain placement using estimation of distribution algorithms. Artif. Intell. Med. 39, 49–63 (2007) · doi:10.1016/j.artmed.2006.04.004 |
| [61] | Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979) |
| [62] | Schlick, T.: Molecular Modelling and Simulation: An Interdisciplinary Guide. Springer, New York (2002) · Zbl 1011.92019 |
| [63] | Schoenberg, I.J.: Remarks to Maurice Fréchet’s article ”sur la définition axiomatique d’une classe d’espaces distanciés vectoriellement applicable sur l’espace de Hilbert”. Ann. Math. 36(3), 724–732 (1935) · Zbl 0012.30703 · doi:10.2307/1968654 |
| [64] | So, M.-C., Ye, Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007) · Zbl 1278.90482 · doi:10.1007/s10107-006-0040-1 |
| [65] | Trosset, M.: Applications of multidimensional scaling to molecular conformation. Comput. Sci. Stat. 29, 148–152 (1998) |
| [66] | Wang, L., Mettu, R., Donald, B.R.: An algebraic geometry approach to protein structure determination from nmr data. In: Proceedings of the Computational Systems Bioinformatics Conference. IEEE Press, New York (2005) |
| [67] | Wu, D., Wu, Z.: An updated geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data. J. Glob. Optim. 37, 661–673 (2007) · Zbl 1119.92032 · doi:10.1007/s10898-006-9080-6 |
| [68] | Wu, D., Wu, Z., Yuan, Y.: Rigid versus unique determination of protein structures with geometric buildup. Optim. Lett. 2(3), 319–331 (2008) · Zbl 1144.92017 · doi:10.1007/s11590-007-0060-7 |
| [69] | Zou, Z., Bird, R., Schnabel, R.: A stochastic/perturbation global optimization algorithm for distance geometry problems. J. Glob. Optim. 11, 91–105 (1997) · Zbl 0891.90173 · doi:10.1023/A:1008244930007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
