The discretizable molecular distance geometry problem

DOI10.1007/S10589-011-9402-6zbMATH Open1259.90153arXivq-bio/0608012OpenAlexW1972865089WikidataQ62562164 ScholiaQ62562164MaRDI QIDQ694593FDOQ694593

Authors: Leo Liberti, Antonio Mucherino, Carlile Lavor, Nelson Maculan 

Publication date: 13 December 2012

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: Given a weighted undirected graph $G=(V,E,d)$, the Molecular Distance Geometry Problem (MDGP) is that of finding a function $x:Gomathbb{R}^3$, where $||x(u)-x(v)||=d(u,v)$ for each $u,vinE$. 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 extbf{NP}-complete and we propose an algorithm, called Branch-and-Prune (BP), which solves the DMDGP exactly. The BP algorithm performs exceptionally well in terms of solution accuracy and can find all solutions to any DMDGP instance. We successfully test the BP algorithm on several randomly generated instances.

Full work available at URL: https://arxiv.org/abs/q-bio/0608012

Recommendations

• Recent advances on the discretizable molecular distance geometry problem
• On the number of solutions of the discretizable molecular distance geometry problem
• Molecular distance geometry methods: from continuous to discrete
• Geometric algebra to describe the exact discretizable molecular distance geometry problem for an arbitrary dimension
• A quantum approach to the discretizable molecular distance geometry problem
• Solving Molecular Distance Geometry Problems Using a Continuous Optimization Approach
• Constraint programming approaches for the discretizable molecular distance geometry problem
• Distance geometry for realistic molecular conformations
• Unassigned distance geometry and molecular conformation problems
• Computational Experience with the Molecular Distance Geometry Problem

zbMATH Keywords

proteindistance geometrybranch-and-prunemolecular conformationNMR

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Explicit sensor network localization using semidefinite representations and facial reductions
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• An updated geometric build-up algorithm for solving the molecular distance geometry problems with sparse distance data
• Generic global rigidity
• An Alternating Projection Algorithm for Computing the Nearest Euclidean Distance Matrix
• The Molecule Problem: Exploiting Structure in Global Optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances
• Equality relating Euclidean distance cone to positive semidefinite cone
• Rigid versus unique determination of protein structures with geometric buildup
• Large-Scale Molecular Optimization from Distance Matrices by a D.C. Optimization Approach
• The lattice of faces of a finite dimensional cone
• Reconstructing a three-dimensional model with arbitrary errors
• Global Continuation for Distance Geometry Problems
• On generating instances for the modular distance geometry problem
• Solving molecular distance geometry problems by global optimization algorithms
• Molecular modeling and simulation. An interdisciplinary guide
• A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
• Theory of semidefinite programming for sensor network localization
• Double variable neighbourhood search with smoothing for the molecular distance geometry problem
• Computational Experience with the Molecular Distance Geometry Problem
• Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem
• The Solution of the Metric STRESS and SSTRESS Problems in Multidimensional Scaling Using Newtons Method
• A stochastic/perturbation global optimization algorithm for distance geometry problems
• Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and D.C. programming
• Distance geometry optimization for protein structures
• A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
• A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
• Title not available (Why is that?)
• Extending the geometric build-up algorithm for the molecular distance geometry problem
• A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data
• On the computation of protein backbones by using artificial backbones of hydrogens
• Recent advances on the discretizable molecular distance geometry problem
• Rigid and Flexible Frameworks
• The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
• Discretization orders for distance geometry problems
• Molecular distance geometry methods: from continuous to discrete
• On the definition of artificial backbones for the discretizable molecular distance geometry problem
• MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
• Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems
• On the number of solutions of the discretizable molecular distance geometry problem
• An interior-point method for approximate positive semidefinite completions
• Structural bioinformatics. An algorithmic approach

Cited In (71)

• An impossible combinatorial counting method in distance geometry
• A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems
• NMR protein structure calculation and sphere intersections
• A study on the covalent geometry of proteins and its impact on distance geometry
• Cycle-based formulations in distance geometry
• Distance Geometry on the Sphere
• On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
• On the embedding of cone graphs in the line with distinct distances between neighbors
• Oriented conformal geometric algebra and the molecular distance geometry problem
• Realizing Euclidean distance matrices by sphere intersection
• Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
• Title not available (Why is that?)
• The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
• Efficient development of competitive Mathematica solutions based on geometric algebra with GAALOPWeb
• Double variable neighbourhood search with smoothing for the molecular distance geometry problem
• On the polynomiality of finding \(^K\text{DMDGP}\) re-orders
• Recent advances on the interval distance geometry problem
• A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances
• Constraint programming approaches for the discretizable molecular distance geometry problem
• Solving a generalized distance geometry problem for protein structure determination
• The \(K\)-discretization and \(K\)-incident graphs for discretizable distance geometry
• A least-squares approach for discretizable distance geometry problems with inexact distances
• Extending the geometric build-up algorithm for the molecular distance geometry problem
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• Molecular distance geometry methods: from continuous to discrete
• Minimal NMR distance information for rigidity of protein graphs
• On the computation of protein backbones by using artificial backbones of hydrogens
• A constrained interval approach to the generalized distance geometry problem
• On the number of solutions of the discretizable molecular distance geometry problem
• Boolean combination of circular arcs using orthogonal spheres
• Optimal partial discretization orders for discretizable distance geometry
• Distance geometry and data science
• Solving Distance Geometry Problem with Inexact Distances in Integer Plane
• MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
• Solving Partial Differential Equations on Manifolds From Incomplete Interpoint Distance
• A quantum approach to the discretizable molecular distance geometry problem
• Unassigned distance geometry and molecular conformation problems
• Diagonally Dominant Programming in Distance Geometry
• Optimal Discretization Orders for Distance Geometry: A Theoretical Standpoint
• On distance graph coloring problems
• Geometric algebra to describe the exact discretizable molecular distance geometry problem for an arbitrary dimension
• On a Relationship Between Graph Realizability and Distance Matrix Completion
• A new algorithm for the \(^K\)DMDGP subclass of distance geometry problems with exact distances
• A note on the Cayley-Menger determinant and the molecular distance geometry problem
• A symmetry-based splitting strategy for discretizable distance geometry problems
• On the optimality of finding DMDGP symmetries
• A NOTE ON COMPUTING THE INTERSECTION OF SPHERES IN
• Discretization orders and efficient computation of Cartesian coordinates for distance geometry
• Discretization vertex orders in distance geometry
• Discretization orders for distance geometry problems
• On the Exact Solution of the Distance Geometry with Interval Distances in Dimension 1
• An application-based characterization of dynamical distance geometry problems
• Discretization orders for protein side chains
• Improving the sampling process in the interval branch-and-prune algorithm for the discretizable molecular distance geometry problem
• Calculating the possible conformations arising from uncertainty in the molecular distance geometry problem using constraint interval analysis
• Solving molecular distance geometry problems by global optimization algorithms
• Solving Molecular Distance Geometry Problems Using a Continuous Optimization Approach
• Title not available (Why is that?)
• A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
• Recent advances on the discretizable molecular distance geometry problem
• The determination of point groups from imprecise molecular geometries
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
• On generating instances for the modular distance geometry problem
• Clifford algebra and the discretizable molecular distance geometry problem
• An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization
• The discretizable distance geometry problem
• New error measures and methods for realizing protein graphs from distance data
• The referenced vertex ordering problem: theory, applications, and solution methods
• An integer programming approach for the search of discretization orders in distance geometry problems
• Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem
• Molecular embedding via a second order dissimilarity parameterized approach

Uses Software

• SNLSDP
• MD-jeep
• Algorithm 97

This page was built for publication: The discretizable molecular distance geometry problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q694593)