The discretizable molecular distance geometry problem
From MaRDI portal
Abstract: Given a weighted undirected graph , the Molecular Distance Geometry Problem (MDGP) is that of finding a function , where for each . 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.
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
Cites work
- scientific article; zbMATH DE number 841192 (Why is no real title available?)
- scientific article; zbMATH DE number 2188749 (Why is no real title available?)
- scientific article; zbMATH DE number 3080144 (Why is no real title available?)
- 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
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data
- A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances
- A stochastic/perturbation global optimization algorithm for distance geometry problems
- An Alternating Projection Algorithm for Computing the Nearest Euclidean Distance Matrix
- An interior-point method for approximate positive semidefinite completions
- An updated geometric build-up algorithm for solving the molecular distance geometry problems with sparse distance data
- Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem
- Computational Experience with the Molecular Distance Geometry Problem
- Discretization orders for distance geometry problems
- Distance geometry optimization for protein structures
- Double variable neighbourhood search with smoothing for the molecular distance geometry problem
- Equality relating Euclidean distance cone to positive semidefinite cone
- Explicit sensor network localization using semidefinite representations and facial reductions
- Extending the geometric build-up algorithm for the molecular distance geometry problem
- Generic global rigidity
- Global Continuation for Distance Geometry Problems
- Large-Scale Molecular Optimization from Distance Matrices by a D.C. Optimization Approach
- MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
- Molecular distance geometry methods: from continuous to discrete
- Molecular modeling and simulation. An interdisciplinary guide
- On generating instances for the modular distance geometry problem
- On the computation of protein backbones by using artificial backbones of hydrogens
- On the definition of artificial backbones for the discretizable molecular distance geometry problem
- On the number of solutions of the discretizable molecular distance geometry problem
- Recent advances on the discretizable molecular distance geometry problem
- Reconstructing a three-dimensional model with arbitrary errors
- Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
- Rigid and Flexible Frameworks
- Rigid versus unique determination of protein structures with geometric buildup
- Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and D.C. programming
- Solving molecular distance geometry problems by global optimization algorithms
- Some properties for the Euclidean distance matrix and positive semidefinite matrix completion problems
- Structural bioinformatics. An algorithmic approach
- The Molecule Problem: Exploiting Structure in Global Optimization
- The Solution of the Metric STRESS and SSTRESS Problems in Multidimensional Scaling Using Newtons Method
- The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
- The lattice of faces of a finite dimensional cone
- Theory of semidefinite programming for sensor network localization
Cited in
(78)- On the hardness of energy minimisation for crystal structure prediction
- NMR protein structure calculation and sphere intersections
- A constrained interval approach to the generalized distance geometry problem
- An impossible combinatorial counting method in distance geometry
- Boolean combination of circular arcs using orthogonal spheres
- Is the distance geometry problem in NP?
- A study on the covalent geometry of proteins and its impact on distance geometry
- Diagonally dominant programming in distance geometry
- An application-based characterization of dynamical distance geometry problems
- Cycle-based formulations in distance geometry
- The determination of point groups from imprecise molecular geometries
- A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems
- MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
- Optimal Discretization Orders for Distance Geometry: A Theoretical Standpoint
- Improving the sampling process in the interval branch-and-prune algorithm for the discretizable molecular distance geometry problem
- Constraint programming approaches for the discretizable molecular distance geometry problem
- On generating instances for the modular distance geometry problem
- Solving partial differential equations on manifolds from incomplete interpoint distance
- On the computation of protein backbones by using artificial backbones of hydrogens
- Distance geometry on the sphere
- Discretization vertex orders in distance geometry
- A least-squares approach for discretizable distance geometry problems with inexact distances
- Calculating the possible conformations arising from uncertainty in the molecular distance geometry problem using constraint interval analysis
- scientific article; zbMATH DE number 811530 (Why is no real title available?)
- On the exact solution of the distance geometry with interval distances in dimension 1
- A new algorithm for the \(^K\mathrm{DMDGP}\) subclass of distance geometry problems with exact distances
- A quantum approach to the discretizable molecular distance geometry problem
- Solving Molecular Distance Geometry Problems Using a Continuous Optimization Approach
- Solving a generalized distance geometry problem for protein structure determination
- On the polynomiality of finding \(^K\text{DMDGP}\) re-orders
- The discretizable molecular distance geometry problem seems easier on proteins
- Recent advances on the interval distance geometry problem
- A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances
- 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
- Optimal partial discretization orders for discretizable distance geometry
- On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
- The referenced vertex ordering problem: theory, applications, and solution methods
- Extending the geometric build-up algorithm for the molecular distance geometry problem
- Discretization orders for distance geometry problems
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- Solving molecular distance geometry problems by global optimization algorithms
- An integer programming approach for the search of discretization orders in distance geometry problems
- Clifford algebra and the discretizable molecular distance geometry problem
- On distance graph coloring problems
- The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
- The discretizable distance geometry problem
- Unassigned distance geometry and molecular conformation problems
- scientific article; zbMATH DE number 2188749 (Why is no real title available?)
- Feasibility check for the distance geometry problem: an application to molecular conformations
- Distance geometry and data science
- On the number of solutions of the discretizable molecular distance geometry problem
- A note on computing the intersection of spheres in \(\mathbb{R}^n\)
- The \(K\)-discretization and \(K\)-incident graphs for discretizable distance geometry
- Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem
- On the number of realizations of certain Henneberg graphs arising in protein conformation
- Recent advances on the discretizable molecular distance geometry problem
- Efficient development of competitive Mathematica solutions based on geometric algebra with GAALOPWeb
- On a relationship between graph realizability and distance matrix completion
- Solving distance geometry problem with inexact distances in integer plane
- Tuning interval branch-and-prune for protein structure determination
- Using a distributed SDP approach to solve simulated protein molecular conformation problems
- Molecular distance geometry methods: from continuous to discrete
- Geometric algebra to describe the exact discretizable molecular distance geometry problem for an arbitrary dimension
- New error measures and methods for realizing protein graphs from distance data
- An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- Discretization orders for protein side chains
- Minimal NMR distance information for rigidity of protein graphs
- 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
- Molecular embedding via a second order dissimilarity parameterized approach
- A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
- Discretization orders and efficient computation of Cartesian coordinates for distance geometry
- Double variable neighbourhood search with smoothing for the molecular distance geometry problem
- Solving the discretizable molecular distance geometry problem by multiple realization trees
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)
