Energy-based Pruning Devices For The Bp Algorithm Applied To Distance Geometry

The Molecular Distance Geometry Problem (MDGP) is the one of finding an embedding of a molecular graph in the three dimensional space, where graph vertices represent atoms and edges represent known distances between some pairs of atoms. The MDGP is a constraint satisfaction problem and it is generally cast as a continuous global optimization problem. Moreover, under some assumptions, this optimization problem can be discretized and so that it becomes combinatorial, and it can be solved by a Branch & Prune (BP) algorithm. The solution set found by BP, however, can be very large for some instances, while only the most energetically stable conformations are of interest. In this work, we propose and integrate the BP algorithm with two new energy-based pruning devices. Computational experiments show that the newly added pruning devices are able to improve the performance of the BP algorithm, as well as the quality (in terms of energy) of the conformations in the solution set. © 2013 Polish Information Processing Society.341346Ministry of Science and Higher Eduction,IntelCrippen, G., Havel, T., (1988) Distance Geometry and Molecular Conformation, , New York: John Wiley &SonsMucherino, A., Lavor, C., Liberti, N.M.L., (2013) Distance Geometry: Theory, Methods and Applications, p. 410. , SpringerSaxe, J.B., Embeddability of weighted graphs in k-space is strongly nphard (1979) Proceedings of 17th Allerton Conference in Communications, Control and Computing, Monticello, IL, pp. 480-489Liberti, L., Lavor, C., MacUlan, N., Mucherino, A., Euclidean distance geometry and applications (2013) To Appear in SIAM ReviewLavor, C., Liberti, L., MacUlan, N., Mucherino, A., The discretizable molecular distance geometry problem (2012) Computational Optimization and Applications, 52, pp. 115-146Liberti, L., Lavor, C., Mucherino, A., MacUlan, N., Molecular distance geometry methods: From continuous to discrete (2010) International Transactions in Operational Research, 18, pp. 33-51Lavor, C., Liberti, L., MacUlan, N., Mucherino, A., Recent advances on the discretizable molecular distance geometry problem (2012) European Journal of Operational Research, 219, pp. 698-706Liberti, L., Lavor, C., MacUlan, N., A branch-and-prune algorithm for the molecular distance geometry problem (2008) International Transactions in Operational Research, 15, pp. 1-17Lavor, C., Liberti, L., Mucherino, A., MacUlan, N., On a discretizable subclass of instances of the molecular distance geometry problem (2009) ACM Conference Proceedings, 24th Annual ACM Symposium on Applied Computing, pp. 804-805. , Hawaii, USAMucherino, A., Lavor, C., Malliavin, T., Liberti, L., Nilges, M., MacUlan, N., Influence of pruning devices on the solution of molecular distance geometry problems (2011) Proceedings of the 10th International Symposium on Experimental Algorithms (SEA11), Ser. Lecture Notes in Computer Science, 6630, pp. 206-217. , P. M. Pardalos and S. Rebennack, Eds., Crete, GreeceBondi, A., Van der waals volumes and radii (1964) Journal of Physical Chemistry, 68 (3), pp. 441-451Jones, J.E.L., Cohesion (1931) Proceedings of the Physical Society, 43, pp. 461-482Mucherino, A., Lavor, C., Liberti, L., A symmetry-driven bp algorithm for the discretizable molecular distance geometry problem (2011) IEEE Conference Proceedings, Computational Structural Bioinformatics Workshop (CSBW11), International Conference on Bioinformatics &Biomedicine (BIBM11, pp. 390-395. , Atlanta, GA, USAMucherino, A., Lavor, C., Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem (2012) Journal of Bioinformatics and Computational Biology, 10, pp. 1-15. , 1242009Liberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A., On the number of solutions of the discretizable molecular distance geometry problem (2011) Proceedings of the 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA11), Ser. Lecture Notes in Computer Science, 6831, pp. 322-342Linge, J.P., Nilges, M., Influence of non-bonded parameters on the quality of nmr structures: A new force field for nmr structure calculation (1999) Journal of Biomolecular NMR, 13 (1), pp. 51-59Hamaker, H.C., The london-van der waals attraction between spherical particles (1937) Physica, 4 (10), pp. 1058-1072Malliavin, T.E., Mucherino, A., Nilges, M., Distance geometry in structural biology: New perspectives (2013) Distance Geometry: Theory, Methods and Applications, pp. 329-350. , L. L. N. M. A. Mucherino, C. Lavor, Ed. SpringerBerman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., Bourne, P., The protein data bank (2000) Nucleic Acids Research, 28, pp. 235-242Lavor, C., Liberti, L., Mucherino, A., The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances (2013) Journal of Global Optimization, 56 (3), pp. 855-87