Given a simple weighted undirected graph G=(V,E,d) with d:E→ℝ+, the Molecular Distance Geometry Problem (MDGP) consists in finding an embedding x:V→ℝ3 such that ‖x u −x v ‖=d uv for each {u,v}∈E. 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 NP-hard and we propose a solution algorithm called Branch-and-Prune (BP). The BP algorithm performs remarkably well in practice in terms of speed and solution accuracy, and can be easily modified to find all incongruent solutions to a given DMDGP instance. We show computational results on several artificial and real-life instances.
展开▼
机译：给定具有d：E→ℝ + 的简单加权无向图G =（V，E，d），分子距离几何问题（MDGP）在于找到嵌入x：V→ℝ 3 ，使得每个{u，v}∈E的“ x u -x v ” = d uv 。我们表明，在蛋白质通常可以满足的一些假设下，MDGP可以表示为在离散空间中进行搜索。我们将此MDGP子类称为可离散MDGP（DMDGP）。我们证明DMDGP是NP难的，并且我们提出了一种称为“分支和修剪（BP）”的解决方案算法。 BP算法在速度和解决方案精度方面在实践中表现非常出色，并且可以轻松修改以找到给定DMDGP实例的所有不一致解决方案。我们显示了几个人工和现实情况下的计算结果。
展开▼
