The discretizable molecular distance geometry problem
From MaRDI portal
(Redirected from Publication:694593)
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)- Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem
- On a relationship between graph realizability and distance matrix completion
- Molecular embedding via a second order dissimilarity parameterized approach
- On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
- An impossible combinatorial counting method in distance geometry
- 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
- The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
- scientific article; zbMATH DE number 2188749 (Why is no real title available?)
- The discretizable molecular distance geometry problem seems easier on proteins
- Efficient development of competitive Mathematica solutions based on geometric algebra with GAALOPWeb
- On the hardness of energy minimisation for crystal structure prediction
- Double variable neighbourhood search with smoothing for the molecular distance geometry problem
- A note on computing the intersection of spheres in \(\mathbb{R}^n\)
- Recent advances on the interval distance geometry problem
- On the polynomiality of finding \(^K\text{DMDGP}\) re-orders
- A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances
- On the exact solution of the distance geometry with interval distances in dimension 1
- Solving distance geometry problem with inexact distances in integer plane
- Solving a generalized distance geometry problem for protein structure determination
- Constraint programming approaches for the discretizable molecular distance geometry problem
- The \(K\)-discretization and \(K\)-incident graphs for discretizable distance geometry
- Diagonally dominant programming in distance geometry
- NMR protein structure calculation and sphere intersections
- Extending the geometric build-up algorithm for the molecular distance geometry problem
- A least-squares approach for discretizable distance geometry problems with inexact distances
- A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems
- On the number of realizations of certain Henneberg graphs arising in protein conformation
- Minimal NMR distance information for rigidity of protein graphs
- On the computation of protein backbones by using artificial backbones of hydrogens
- Molecular distance geometry methods: from continuous to discrete
- A constrained interval approach to the generalized distance geometry problem
- Using a distributed SDP approach to solve simulated protein molecular conformation problems
- 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
- MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
- A study on the covalent geometry of proteins and its impact on distance geometry
- A quantum approach to the discretizable molecular distance geometry problem
- Unassigned distance geometry and molecular conformation problems
- Optimal Discretization Orders for Distance Geometry: A Theoretical Standpoint
- Geometric algebra to describe the exact discretizable molecular distance geometry problem for an arbitrary dimension
- On distance graph coloring problems
- A new algorithm for the \(^K\mathrm{DMDGP}\) subclass of distance geometry problems with exact distances
- A note on the Cayley-Menger determinant and the molecular distance geometry problem
- Is the distance geometry problem in NP?
- A symmetry-based splitting strategy for discretizable distance geometry problems
- On the optimality of finding DMDGP symmetries
- Discretization orders and efficient computation of Cartesian coordinates for distance geometry
- Discretization vertex orders in distance geometry
- Solving the discretizable molecular distance geometry problem by multiple realization trees
- Discretization orders for distance geometry problems
- Discretization orders for protein side chains
- An application-based characterization of dynamical distance geometry problems
- 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
- Improving the sampling process in the interval branch-and-prune algorithm for the discretizable molecular distance geometry problem
- Solving Molecular Distance Geometry Problems Using a Continuous Optimization Approach
- Distance geometry on the sphere
- Solving partial differential equations on manifolds from incomplete interpoint distance
- scientific article; zbMATH DE number 811530 (Why is no real title available?)
- Feasibility check for the distance geometry problem: an application to molecular conformations
- A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- Recent advances on the discretizable molecular distance geometry problem
- The determination of point groups from imprecise molecular geometries
- On generating instances for the modular distance geometry problem
- Cycle-based formulations in distance geometry
- Clifford algebra and the discretizable molecular distance geometry problem
- An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization
- New error measures and methods for realizing protein graphs from distance data
- The discretizable distance geometry problem
- Tuning interval branch-and-prune for protein structure determination
- The referenced vertex ordering problem: theory, applications, and solution methods
- An integer programming approach for the search of discretization orders in distance geometry problems
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)
