Leo Liberti

The Molecular Distance Geometry Problem is essential to structural biology, as it seeks to determine three-dimensional protein structures from partial interatomic distances. Its discretizable subclass (DMDGP) admits an exact combinatorial formulation that enables efficient exploration of the search space. However, in practical settings such as Nuclear Magnetic Resonance (NMR) spectroscopy, distances are available only within uncertainty bounds, leading to the interval variant ( i DMDGP). We propose a hybrid combinatorial–continuous framework for solving the i DMDGP. The method combines an enumeration process derived from the DMDGP with a continuous refinement stage that minimizes a nonconvex stress function penalizing deviations from admissible distance intervals. This integration supports a systematic exploration guided by discrete structure and local optimization. The formulation incorporates torsion angle intervals and chirality constraints through an atom ordering that preserves protein-backbone geometry. Numerical experiments show that the approach efficiently reconstructs geometrically valid conformations even under wide distance bounds, whereas most existing studies assume narrow ones.

We consider the problem of minimizing a polynomial f over the (binary) hypercube. We show that, for a specific set of polynomials, their binary nonnegativity (i.e., on the hypercube) can be checked in polynomial time via minimum cut algorithms, from which we construct a linear programming representation for this set of polynomials. We categorize binary polynomials according to their signed support patterns and develop parameterized linear programming representations for binary nonnegative polynomials. This allows the construction of signed certificates of binary nonnegativity with adjustable signed support patterns and representation complexities; and we propose a method for minimizing f by decomposing it as a sum of signed certificates. This method yields new hierarchies of linear programming relaxations for binary polynomial optimization. Moreover, because our decomposition depends only on the support of f, the new hierarchies are sparsity-preserving. Funding: Most of the work done by the first author on this paper occurred while he was a PhD student at Laboratoire d’Informatique de l’École Polytechnique, Centre National de la Recherche Scientifique, École Polytechnique, Institut Polytechnique de Paris (IPP), sponsored by a grant of the IPP doctoral school, for which both authors are grateful.

The Molecular Distance Geometry Problem (MDGP) is essential in structural biology, as it seeks to determine three-dimensional protein structures from partial interatomic distances. Its discretizable subclass (DMDGP) admits an exact combinatorial formulation that enables efficient exploration of the search space. However, in practical settings such as Nuclear Magnetic Resonance (NMR) spectroscopy, distances are available only within uncertainty bounds, leading to the interval variant (\emph{i}DMDGP). We propose a hybrid combinatorial--continuous framework for solving the \emph{i}DMDGP. The method combines an enumeration process derived from the DMDGP with a continuous refinement stage that minimizes a nonconvex stress function that penalizes deviations from admissible distance intervals. This integration supports a systematic exploration guided by discrete structure and local optimization. The formulation incorporates torsion-angle intervals and chirality constraints through a refined atom ordering that preserves protein-backbone geometry. Numerical experiments show that the approach efficiently reconstructs geometrically valid conformations even under wide distance bounds, whereas most existing studies assume narrow ones.

In 1979, James B. Saxe published an extended summary on the complexity of the Distance Geometry Problem in the proceedings of the 17th Allerton Conference [16]. Many of the proofs in his paper are sketches, and even the whole proofs do not have all the details. In this paper we provide a commentary to Saxe's results and hopefully more understandable versions thereof. Note that both sides are squared turn Eq. (1) into a quadratic (polynomial) equation. The EDGP is natively a decision problem; realizations can be used as certificates for YES instances in an appropriate computational model (see Sect. 1.1.1). A realization x can be represented by an n × K matrix, where n = |V | and the v-th row of x is a K-vector representing

The Buckminsterfullerene is an inorganic molecule consisting of 60 carbon atoms in the shape of a soccer ball. It was used in [Juhas et al., Nature 2006] to showcase algorithms that find the correct shape of a protein from limited data (length of inter-atomic distances) without any further chemical experiment: in that case, by means of a complicated constructive heuristic based on genetic algorithms. In this paper we show that we can reconstruct the Buckminsterfullerene structure by means of mathematical programming, standard solver software, and little else.

We survey theoretical, algorithmic, and computational results at the intersection of distance geometry problems and mathematical programming, both with and without adjacencies as part of the input. While mathematical programming methods can solve large-scale distance geometry problems with adjacencies, they are severely challenged in the absence thereof.