The embedding problem for predistance matrices (Q1176717)

For determining the conformation of macromolecules from nuclear magnetic resonance (NMR) spectroscopy, efficient distance geometry programs are necessary. A particularly difficult aspect for these programs, called the embedding problem, is to develop algorithms for finding the coordinates of points in \(R^ 3\) (for chemistry) which generate distances between atoms, these distances being the nearest to those measured by the NMR spectroscopy techniques. The paper proposes an approach to the embedding problem consisting of two stages, called Phase I and Phase II. The Phase I solution is the near point of a convex set to the original given experimental distances. An algorithm, denoted modified alternating projections (MAP), computes this near point. Phase II seeks a solution such that the points which generate the distances are required to lie in \(R^ 3\) (for chemistry). The difficulty of the Phase II comes from the fact that the convexity of the minimizing set and the uniqueness of the solution are lost. Section 4 gives the MAP algorithm which solves Phase I. Since the embedding problem is the distance geometry equivalent of a multiple minima problem, Section 5 gives a compact form of the analytic gradient for speeding up the computation, and a penalty function is added for making the Hessian positive definite at a local minimum. Section 6 shows that all the critical points lie on the surface of a sphere. This is considered as an essential tool for the approach to the multiple minima problem. The effect on solutions under permutations is explored. Section 7 develops the geometry of the cone of distance matrices, including the facial structure, which is used in phase II. Results on the angle that the solutions make with the `center axis' of the cone are obtained. Section 8 presents the Phase II algorithm and the data obtained on a number of randomly generated data matrices, using the two phases.