A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems

Authors:
Open Access
Publisher website
Google Scholar
Abstract
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.
Funding Information
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2013/07375-0)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2022/06745-7)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2023/08706-1)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2024/00923-6)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2024/12967-8)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2024/15980-5)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (2024/21786-7)
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (305227/2022-0)
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (404616/2024-0)
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (302520/2025-2)
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (402609/2025-5)
  • Agence Nationale de la Recherche (ANR-24-CE23-1621-03)

This publication has 46 references indexed in Scilit: