An adaptive branching scheme for the Branch & Prune algorithm applied to Distance Geometry

• Autorzy: Douglas Gonçalves , Antonio Mucherino , Carlile Lavor
• Języki publikacji: EN

Abstrakty

EN

The Molecular Distance Geometry Problem (MDGP) is the one of finding molecular conformations that satisfy a set of distance constraints obtained through experimental techniques such as Nuclear Magnetic Resonance (NMR). We consider a subclass of MDGP instances that can be discretized, where the search domain has the structure of a tree, which can be explored by using an interval Branch & Prune (iBP) algorithm. When all available distances are exact, all candidate positions for a given molecular conformation can be enumerated. This is however not possible in presence of interval distances, because a continuous subset of positions can actually be computed for some atoms. The focus of this work is on a new scheme for an adaptive generation of a discrete subset of candidate positions from this continuous subset. Our generated candidate positions do not only satisfy the distances employed in the discretization process, but also additional distances that might be available (the so-called pruning distances). Therefore, this new scheme is able to guide more efficiently the search in the feasible regions of the search domain. In this work, we motivate the development and formally introduce this new adaptive scheme. Presented computational experiments show that iBP, integrated with our new scheme, outperforms the standard iBP on a set of NMR-like instances.(original abstract)

Słowa kluczowe

PL

Fizyka; Algorytmy; Medycyna

EN

Physics; Algorithms; Medicine

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 457-463

Twórcy

autor

Douglas Gonçalves

• University of Rennes, France

autor

Antonio Mucherino

• University of Rennes, France

autor

Carlile Lavor

• IMECC-UNICAMP

Bibliografia

• 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 Acid Research 28, 235-242, 2000.
• Costa V., Mucherino A., Lavor C., Cassioli A., Carvalho L. M., Maculan N., Discretization Orders for Protein Side Chains, to appear in Journal of Global Optimization, 2014.
• Crippen G. M. and Havel T. F., Distance Geometry and Molecular Conformation, John Wiley & Sons, New York, 1988.
• Goncalves D. S., Mucherino A., Discretization Orders and Efficient Computation of Cartesian Coordinates for Distance Geometry, to appear in Optimization Letters, 2014.
• Havel T. F., Distance Geometry, D.M. Grant and R.K. Harris (Eds.), Encyclopedia of Nuclear Magnetic Resonance, Wiley, New York, 1701-1710, 1995.
• Lavor C., Lee J., Lee-St.John A., Liberti L., Mucherino A., Sviridenko M., Discretization Orders for Distance Geometry Problems, Optimization Letters 6(4), 783-796, 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 Branch-and-Prune Algorithm for the Discretizable Molecular Distance Geometry Problem with Inexact Distances, Journal of Global Optimization 56(3), 855-871, 2013.
• Liberti L., Lavor C., Maculan N., Mucherino A., Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3-69, 2014.
• Malliavin T. E., Mucherino A., Nilges M., Distance Geometry in Structural Biology: New Perspectives. In: [13], 329-350, 2013.
• Mucherino A., On the Identification of Discretization Orders for Distance Geometry with Intervals, Lecture Notes in Computer Science 8085, F. Nielsen and F. Barbaresco (Eds.), Proceedings of Geometric Science of Information (GSI13), Paris, France, 231-238, 2013.
• Mucherino A., Lavor C., Liberti L., The Discretizable Distance Geometry Problem, Optimization Letters 6(8), 1671-1686, 2012.
• Mucherino A., Lavor C., Liberti L., Maculan N. (Eds.), Distance Geometry: Theory, Methods and Applications, Springer, 2013.
• Thompson H. B., Calculation of Cartesian Coordinates and their Derivatives from Internal Molecular Coordinates, Journal of Chemical Physics 47, 3407, 1967.