On the computation of protein backbones by using artificial backbones of hydrogens. (English) Zbl 1219.90209
Summary: NMR experiments provide information from which some of the distances between pairs of hydrogen atoms of a protein molecule can be estimated. Such distances can be exploited in order to identify the three-dimensional conformation of the molecule: this problem is known in the literature as the molecular distance geometry problem (MDGP). In this paper, we show how an artificial backbone of hydrogens can be defined which allows the reformulation of the MDGP as a combinatorial problem. This is done with the aim of solving the problem by the branch and prune (BP) algorithm, which is able to solve it efficiently. Moreover, we show how the real backbone of a protein conformation can be computed by using the coordinates of the hydrogens found by the BP algorithm. Formal proofs of the presented results are provided, as well as computational experiences on a set of instances whose size ranges from 60 to 6000 atoms.
MSC:
| 90C90 | Applications of mathematical programming |
| 90C35 | Programming involving graphs or networks |
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
Keywords:
distance geometry; protein molecules; hydrogen atoms; combinatorial optimization; branch and pruneReferences:
| [1] | 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 |
| [2] | Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd Edn., SIAM (1999) · Zbl 0934.65030 |
| [3] | 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, 1251–1277 (2008) · Zbl 1161.49028 · doi:10.1137/05062754X |
| [4] | Carvalho R.S., Lavor C., Protti F.: Extending the geometric buildup 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 |
| [5] | Crippen G.M., Havel T.F.: Distance Geometry and Molecular Conformation. Wiley, New York (1988) · Zbl 1066.51500 |
| [6] | 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 |
| [7] | Engh R.A., Huber R.: Accurate bond and angle parameters for x-ray protein structure refinement. Acta Crystallogr. A47, 392–400 (1991) |
| [8] | 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 |
| [9] | Havel T.F.: Distance geometry. In: Grant, D.M., Harris, R.K. (eds) Encyclopedia of Nuclear Magnetic Resonance, pp. 1701–1710. Wiley, New York (1995) |
| [10] | Kirkpatrick S., Gelatt C.D. Jr, Vecchi M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [11] | Lavor, C.: On generating instances for the molecular distance geometry problem. In: Liberti, L., Maculan, N. (eds.) Global Optimization From Theory to Implementation. Series: Nonconvex Optimization and Its Applications vol. 84, pp. 405–414. Springer (2006) · Zbl 1100.90034 |
| [12] | Lavor, C., Liberti, L., Maculan, N.: Discretizable molecular distance geometry problem. Tech. Rep. q-bio.BM/0608012, arXiv (2006) · Zbl 1129.90389 |
| [13] | Lavor C., Liberti L., Maculan N.: Molecular distance geometry problem. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 2305–2311. Springer, New York (2009) · Zbl 1169.90470 |
| [14] | Lavor, C., Liberti, L., Mucherino, A., Maculan, N.: On a discretizable subclass of instances of the molecular distance geometry problem. In: ACM Conference Proceedings, 24th Annual ACM Symposium on Applied Computing (SAC09), Hawaii USA, pp. 804–805 (2009) · Zbl 1190.92009 |
| [15] | Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: Computing artificial backbones of hydrogen atoms in order to discover protein backbones. In: IEEE Conference Proceedings, International Conference IMCSIT09, Workshop on Combinatorial Optimization (WCO09), Poland, pp. 751–756 (2009) |
| [16] | Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: An artificial backbone of hydrogens for finding the conformation of protein molecules. In: IEEE Conference Proceedings, Computational Structural Bioinformatics Workshop (CSBW09), Washington D.C., USA, pp. 152–155, (2009) |
| [17] | Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: Discrete approaches for solving molecular distance geometry problems using NMR data. Int. J. Comput. Biosci. (2010) (to appear) · Zbl 1219.90177 |
| [18] | 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) · Zbl 1136.92037 · doi:10.1111/j.1475-3995.2007.00622.x |
| [19] | 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 |
| [20] | Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. (2010) (to appear) · Zbl 1219.90177 |
| [21] | Moré J.J., Wu Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7, 814–836 (1997) · Zbl 0891.90168 · doi:10.1137/S1052623495283024 |
| [22] | 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 |
| [23] | Mucherino, A., Lavor, C.: The Branch and Prune algorithm for the molecular distance geometry problem with inexact distances, World Academy of Science, Engineering and Technology (WASET). In: Proceedings of the ”International Conference on Bioinformatics and Biomedicine” (ICBB09), Venice, Italy (2009) · Zbl 1272.90074 |
| [24] | 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 (CTW09), pp. 337–340, Paris (2009) |
| [25] | Mucherino A., Lavor C., Liberti L., Maculan N.: On the definition of artificial backbones for the discretizable molecular distance geometry problem. Math. Balkanica 23(3–4), 289–302 (2009) · Zbl 1190.92009 |
| [26] | Mucherino, A., Liberti, L., Lavor, C., Maculan, N.: Comparisons between an exact and a MetaHeuristic algorithm for the molecular distance geometry problem. In: ACM Conference Proceedings, Genetic and Evolutionary Computation Conference (GECCO09), Montréal, Canada, pp. 333–340 (2009) · Zbl 1190.92009 |
| [27] | Mucherino, A., Liberti, L., Lavor, C.: $${{\(\backslash\)tt MD-jeep}}$$ : an implementation of a Branch & Prune algorithm for distance geometry problems, LNCS series. In: Proceedings of the Third International Congress on Mathematical Software (ICMS10), Kobe, Japan (2010) · Zbl 1294.68144 |
| [28] | 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, Monticello, IL, pp. 480–489 (1979) |
| [29] | Schlick T.: Molecular Modelling and Simulation: An Interdisciplinary Guide. Springer, New York (2002) · Zbl 1011.92019 |
| [30] | Schwieters C.D., Kuszewski J.J., Clore G.M.: Using Xplor-NIH for NMR molecular structure determination. Prog. Nucl. Magn. Reson. Spectrosc. 48, 47–62 (2006) · doi:10.1016/j.pnmrs.2005.10.001 |
| [31] | 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 |
| [32] | Wu D., Wu Z., Yuan Y.: Rigid versus unique determination of protein structures with geometric buildup. Optim. Lett. 2, 319–331 (2008) · Zbl 1144.92017 · doi:10.1007/s11590-007-0060-7 |
| [33] | Xu H., Izrailev S., Agrafiotis D.K.: Conformational sampling by self-organization. J. Chem. Inf. Comput. Sci. 43, 1186–1191 (2003) |
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.
