New Methods for Distance Geometry Problems

距离几何问题的新方法

• 批准号: 13650063
• 负责人: YAJIMA Yasutoshi
• 金额: $ 2.11万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13650063/
• 关键词: Distance Geometry; Molecular Conformation; Positive Semidefinite Programming; 大域的最適化; 非凸2次計画問題; 半正定値計画; 大域的的最適化

We consider distance geometry problems for determining $r$--dimensional coordinates of $n$ points from a given set of the distances between the points. This problem is a fundamental problem in molecular biology for finding the structure of proteins from NMR (Nuclear Magnetic Resonance) data.We formulate the problem as the minimization of an error function defined by the sum of the absolute differences, which is a typical nonconvex optimization problem. We show that this problem can be reduced into a concave quadratic minimization problem. We propose positive semidefinite relaxations as well as local search procedures for this problem. Our numerical results show that we can generate acceptable solutions of the problem with up to 800 points.

我们考虑确定$ r $的距离几何问题 - 从给定的一组点之间的一组距离$ n $点的尺寸坐标。这个问题是分子生物学中的一个基本问题，用于从NMR（核磁共振）数据中找到蛋白质的结构。我们将问题提出为最小化的误差函数，这是由绝对差异的总和定义的，这是典型的非convex优化问题。我们表明，可以将这个问题简化为凹二次最小化问题。我们提出了积极的半决赛放松以及解决此问题的本地搜索程序。我们的数值结果表明，我们可以使用多达800点生成可接受的解决方案。