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
- A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
- 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
- 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?)
- 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 interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
- The lattice of faces of a finite dimensional cone
- The Molecule Problem: Exploiting Structure in Global Optimization
- The Solution of the Metric STRESS and SSTRESS Problems in Multidimensional Scaling Using Newtons Method
- Theory of semidefinite programming for sensor network localization
Cited in
(79)- Double variable neighbourhood search with smoothing for the molecular distance geometry problem
- A symmetry-based splitting strategy for discretizable distance geometry problems
- Recent advances on the interval distance geometry problem
- Realizing Euclidean distance matrices by sphere intersection
- Minimal NMR distance information for rigidity of protein graphs
- On the embedding of cone graphs in the line with distinct distances between neighbors
- Oriented conformal geometric algebra and the molecular distance geometry problem
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- Tuning interval branch-and-prune for protein structure determination
- The discretizable distance geometry problem
- Recent advances on the discretizable molecular distance geometry problem
- On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
- A new algorithm for the \(^K\mathrm{DMDGP}\) subclass of distance geometry problems with exact distances
- The determination of point groups from imprecise molecular geometries
- A quantum approach to the discretizable molecular distance geometry problem
- A note on the Cayley-Menger determinant and the molecular distance geometry problem
- Unassigned distance geometry and molecular conformation problems
- The referenced vertex ordering problem: theory, applications, and solution methods
- A least-squares approach for discretizable distance geometry problems with inexact distances
- An integer programming approach for the search of discretization orders in distance geometry problems
- The \(K\)-discretization and \(K\)-incident graphs for discretizable distance geometry
- A constrained interval approach to the generalized distance geometry problem
- An application-based characterization of dynamical distance geometry problems
- Distance geometry and data science
- Efficient development of competitive Mathematica solutions based on geometric algebra with GAALOPWeb
- NMR protein structure calculation and sphere intersections
- On the optimality of finding DMDGP symmetries
- Geometric algebra to describe the exact discretizable molecular distance geometry problem for an arbitrary dimension
- On the polynomiality of finding \(^K\text{DMDGP}\) re-orders
- Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem
- The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances
- Boolean combination of circular arcs using orthogonal spheres
- On the number of realizations of certain Henneberg graphs arising in protein conformation
- Improving the sampling process in the interval branch-and-prune algorithm for the discretizable molecular distance geometry problem
- Solving distance geometry problem with inexact distances in integer plane
- Optimal partial discretization orders for discretizable distance geometry
- Diagonally dominant programming in distance geometry
- The discretizable molecular distance geometry problem seems easier on proteins
- Is the distance geometry problem in NP?
- Solving the discretizable molecular distance geometry problem by multiple realization trees
- Solving Molecular Distance Geometry Problems Using a Continuous Optimization Approach
- Using a distributed SDP approach to solve simulated protein molecular conformation problems
- Distance geometry on the sphere
- An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization
- Molecular distance geometry methods: from continuous to discrete
- Optimal Discretization Orders for Distance Geometry: A Theoretical Standpoint
- A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem
- Molecular embedding via a second order dissimilarity parameterized approach
- Solving a generalized distance geometry problem for protein structure determination
- On a relationship between graph realizability and distance matrix completion
- A note on computing the intersection of spheres in \(\mathbb{R}^n\)
- On the exact solution of the distance geometry with interval distances in dimension 1
- Discretization orders and efficient computation of Cartesian coordinates for distance geometry
- scientific article; zbMATH DE number 811530 (Why is no real title available?)
- Discretization orders for protein side chains
- Discretization vertex orders in distance geometry
- Assigned and unassigned distance geometry: applications to biological molecules and nanostructures
- New error measures and methods for realizing protein graphs from distance data
- On the number of solutions of the discretizable molecular distance geometry problem
- Feasibility check for the distance geometry problem: an application to molecular conformations
- Solving partial differential equations on manifolds from incomplete interpoint distance
- On the computation of protein backbones by using artificial backbones of hydrogens
- scientific article; zbMATH DE number 2188749 (Why is no real title available?)
- On generating instances for the modular distance geometry problem
- MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems
- On the hardness of energy minimisation for crystal structure prediction
- 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
- On distance graph coloring problems
- Cycle-based formulations 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
- A study on the covalent geometry of proteins and its impact on distance geometry
- An impossible combinatorial counting method in distance geometry
- Discretization orders for distance geometry problems
- Erratum to: ``Discretization vertex orders in distance geometry: Finding repetition orders is in \textbf{P} (even if \(K = 1\))
- 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
- Clifford algebra and the discretizable molecular distance geometry problem
- Extending the geometric build-up algorithm for the molecular distance geometry problem
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)
