A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems
L. D. Secchin, W. da Rocha, M. da Rosa, L. Liberti, C. Lavor · 2025
Read A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems by L. D. Secchin, W. da Rocha, M. da Rosa, L. Liberti, C. Lavor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19970.txt.
Introduction
Leonardo D. Secchin and four co-authors attack the molecular distance geometry problem under realistic doubt. The task is to rebuild a protein's 3D shape from partial distance data, such as NMR measurements provide. Exact methods exist when distances are precise, exploiting a discrete ordering of atoms. Real distances, though, come as intervals, which breaks the exact machinery.
Their hybrid strategy runs the combinatorial enumeration from the discretizable problem. It then polishes each candidate with a continuous step that penalizes distances straying outside their allowed ranges. Torsion angle ranges and chirality constraints are folded into the atom ordering, to respect backbone shape. Experiments show valid structures recovered even under wide distance bounds, where most earlier studies assumed narrow ones.
Catalog record
| CREATOR | L. D. Secchin, W. da Rocha, M. da Rosa, L. Liberti, C. Lavor |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19970
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems Thanks: This research was partially funded by the Brazilian research agencies FAPESP (grant numbers 2013/07375-0, 2022/06745-7, 2023/08706-1, 2024/00923-6, 2024/12967-8, 2024/15980-5, 2024/21786-7) and CNPq (grant numbers 305227/2022-0, 404616/2024-0, 302520/2025-2, 402609/2025-5). L. D. Secchin, W. da Rocha, M. da Rosa, L. Liberti, C. Lavor Abstract 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 ( 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 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. keywords: Molecular Distance Geometry Problem, Spectral Projected Gradient Algorithm, 3D Protein Structure, Nuclear Magnetic Resonance 1 Introduction The Molecular Distance Geometry Problem (MDGP) aims to determine the three-dimensional configuration of a protein molecule consistent with interatomic distance constraints from stereochemistry and Nuclear Magnetic Resonance (NMR) experiments. Typically, only a subset of pairwise distances is available [ 31 ] . Formally, let G=(V,E,d) be a weighted graph where V denotes atoms, E\subseteq V\times V the pairs with known distances, and d:E\to\mathbb{R}_{>0} assigns those distances. The MDGP asks for a realization x:V\to\mathbb{R}^{3} such that \|x_{u}-x_{v}\|=d_{u,v},\qquad\forall\{u,v\}\in E, with \|\cdot\| the Euclidean norm. A well-studied subclass, the Discretizable MDGP (DMDGP), is NP-hard [ 27 , 31 ] yet exhibits rich combinatorial structure [ 29 , 32 ] . Under an appropriate atom ordering and stereochemical constraints, the DMDGP search space can be represented by a binary search tree that can be explored by the Branch-and-Prune (BP) algorithm [ 30 ] . In this setting, the protein backbone geometry, parameterized by torsion angles \phi,\ \psi,\ \omega [ 16 ] , is modeled using covalent bond lengths d_{i-1,i} and distances across two bonds d_{i-2,i} given a priori [ 37 ] . From NMR chemical shifts, approximate \phi,\ \psi values can be inferred [ 39 ] , and typical \omega values are available in structural data [ 37 ] , which can be converted into distances across three bonds ( d_{i-3,i} ) [ 30 ] , and completes the model. To incorporate proximity information from NMR Nuclear Overhauser Effect Spectroscopy (NOESY) (long-range constraints between spatially close hydrogen atoms, <5 Å) [ 25 ] , we include backbone-bound hydrogen atoms ( H_{N} , H_{\alpha} ) together with N , C_{\alpha} , and C . Because this extension breaks the single-chain structure, we adopt an augmented atom ordering that allows repeated atoms and explicitly includes hydrogen atoms [ 26 ] . This ordering also guides BP exploration, since many hydrogen-related constraints span three or more bonds [ 13 , 30 ] . Several alternative orderings exist, see e.g. [ 22 , 31 ] . In our approach, we employ one that facilitates the representation of torsion angle intervals. Nevertheless, for didactic reasons and to avoid unnecessary technical detail, we adopt the well-established DMDGP ordering [ 27 ] , which simplifies both the exposition and the theoretical development. Uncertainties in NMR experiments motivate the interval variant ( i DMDGP) [ 28 ] , where each \{i,j\}\in E is associated with bounds [d^{L}_{i,j},\,d^{U}_{i,j}] and one seeks x:V\to\mathbb{R}^{3} satisfying d^{L}_{i,j}\leq\|x_{i}-x_{j}\|\leq d^{U}_{i,j},\qquad\forall\{i,j\}\in E. Thus, the i DMDGP searches for a configuration X=[x_{1},\ldots,x_{n}]\in\mathbb{R}^{3\times n} consistent with interval constraints, which is inherently more challenging than the exact case (from now on, if d_{i,j}^{L}=d_{i,j}^{U} we call d_{i,j} an exact distance ; if d_{i,j}^{L}<d_{i,j}^{U} , we call it an interval distance ). To illustrate the i DMDGP, we consider a toy instance consisting of ten atoms. By definition, the distances d_{i-1,i} , d_{i-2,i} , d_{i-3,i} are specified for each admissible index i in the DMDGP ordering ( 4\leq i\leq 10 ). In this example, we additionally assume that NMR experiments detect interactions between the atom pairs \{1,8\} , \{2,10\} , and \{3,9\} , providing estimates for the corresponding interatomic distances. The distance matrix for this instance is organized as follows: the distances d_{i-1,i} and d_{i-2,i} are exact; all other experimentally determined entries (the “extra distances”) are given as intervals; and unknown entries are denoted by “ ? ”, indicating pairs for which no measurement is available. For brevity, we display only the upper triangular part of the symmetric matrix: \left[\begin{array}[]{cccccccccc}0&d_{1,2}&d_{1,3}&[d_{1,4}^{L},d_{1,4}^{U}]&?&?&?&[d_{1,8}^{L},d_{1,8}^{U}]&?&?\\ &0&d_{2,3}&d_{2,4}&[d_{2,5}^{L},d_{2,5}^{U}]&?&?&?&?&[d_{2,10}^{L},d_{2,10}^{U}]\\ &&0&d_{3,4}&d_{3,5}&[d_{3,6}^{L},d_{3,6}^{U}]&?&?&[d_{3,9}^{L},d_{3,9}^{U}]&?\\ &&&0&d_{4,5}&d_{4,6}&[d_{4,7}^{L},d_{4,7}^{U}]&?&?&?\\ &&&&0&d_{5,6}&d_{5,7}&[d_{5,8}^{L},d_{5,8}^{U}]&?&?\\ &&&&&0&d_{6,7}&d_{6,8}&[d_{6,9}^{L},d_{6,9}^{U}]&?\\ &&&&&&0&d_{7,8}&d_{7,9}&[d_{7,10}^{L},d_{7,10}^{U}]\\ &&&&&&&0&d_{8,9}&d_{8,10}\\ &&&&&&&&0&d_{9,10}\\ &&&&&&&&&0\\ \end{array}\right]. In most continuous approaches to distance-related problems [ 14 , 19 , 21 ] , it is assumed that the distance intervals are narrow. In contrast, our framework considers a scenario closer to that observed in NMR experiments, where distance uncertainties are typically wider. In this work we develop a hybrid combinatorial–continuous framework for the i DMDGP that integrates the enumerative strategy of [ 28 ] with a continuous formulation in the spirit of [ 20 ] . The method couples (i) an enumeration process based on the DMDGP search tree with (ii) a continuous optimization problem whose constraints measures violations of admissible intervals. This constitutes a practical step toward scalable hybrid algorithms for realistic i DMDGP instances. 2 Problem formulation and modeling assumptions We summarize the modeling assumptions and notation used throughout the paper, postponing solver-dependent choices and placement formulas to Sections 3.1 and 4 . Backbone geometry and atom ordering We treat the protein backbone as a known sequence of residues with covalent bond lengths and bond angles fixed to standard values [ 16 , 18 ] . Variability arises solely from torsion angles. Long-range interatomic distances (typically from NMR) are represented as intervals, whereas distances across one or two covalent bonds are considered exact. To encode these relations, we adopt an i DMDGP ordering with repetitions of atoms, similar to [ 26 ] , which allows us to explicitly include backbone-bound hydrogen atoms 1 1 1 For proline, the peptide nitrogen is not bound to a hydrogen; we replace H_{N}^{i} by a \delta -hydrogen attached to C_{\delta} . For glycine, whose C_{\alpha} is bonded to two hydrogen atoms, only one is retained for modeling purposes. ( H_{N} , H_{\alpha} ) and to couple torsion information with distance constraints through consecutive quadruples. This ordering is convenient for representing chirality and other orientation-dependent geometric properties, and it aligns with the discrete primitives used later (see Section 3.1 ). Torsion-angle domains and chirality Let \tau_{i} denote the torsion angle associated with the i th quadruple of consecutive atoms in the ordering. Its feasible set is either a single interval, \mathcal{T}_{i}=[\tau_{i}^{L},\tau_{i}^{U}], or the union of two symmetric intervals, \mathcal{T}_{i}=[-\tau_{i}^{U},-\tau_{i}^{L}]\ \cup\ [\tau_{i}^{L},\tau_{i}^{U}], depending on whether one or both orientations (signs) are admissible. We write \tau=(\tau_{1},\ldots,\tau_{m})\in\mathcal{T} to indicate \tau_{i}\in\mathcal{T}_{i} for all i . In Section 3.1 we exploit the