Polynomial cases of the Discretizable Molecular Distance Geometry Problem

2011/03/07 by Leo Liberti, Liberti, Leo, Carlile Lavor +5
Computer Science · #Computational Drug Discovery Methods #Computational Engineering #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Finance #Quantitative Methods (q-bio.QM) #and Science (cs.CE)

paper · pdf · doi:10.48550/arxiv.1103.1264

openalex publication_date 2011/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An important application of distance geometry to biochemistry studies the embeddings of the vertices of a weighted graph in the three-dimensional Euclidean space such that the edge weights are equal to the Euclidean distances between corresponding point pairs. When the graph represents the backbone of a protein, one can exploit the natural vertex order to show that the search space for feasible embeddings is discrete. The corresponding decision problem can be solved using a binary tree based search procedure which is exponential in the worst case. We discuss assumptions that bound the search tree width to a polynomial size.

Related

• The Discretizable Molecular Distance Geometry Problem
• An impossible utopia in distance geometry
• A Clifford Algebra approach to the Discretizable Molecular Distance Geometry Problem
• A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems
• On the Complexity of the Ordered Covering Problem in Distance Geometry