The Molecule Problem: Determining Conformation from Pairwise Distances

The molecule problem is that of determining the coordinates of a set of points in space from a (usually sparse) set of pairwise distance measurements. As its name implies, it has applications in the determination of molecular conformation. Unfortunately, the molecule problem is NP-hard. We present an approach to the molecule problem that uses a very specialized divide-and-conquer technique. Instead of solving a single large problem we try to solve a sequence of smaller, presumably easier ones. These small problems consist of subsets of points whose relative locations can be determined uniquely. Once such a subset is positioned, its points can collectively be treated as a rigid body. This can greatly reduce the number of degrees of freedom in the problem. Identifying subsets of points whose relative locations can be uniquely determined requires exploiting some very special structure inherent in the molecule problem. We reduce this identification to a purely combinatoric characterization that ignores the actual distances. We develop necessary graph theoretic conditions for a set of points to have a unique solution, along with efficient algorithms to find subgraphs with these properties. These characterizations and algorithms combine ideas from matching theory, differential topology and matrix computations. These ideas have been implemented in ABBIE, a program to solve three-dimensional instances of the molecule problem. ABBIE combines the recursive decomposition described above with a nonlinear global optimizer to perform the coordinate determinations. Detail of this implementation are described, and numerical results of simulated chemical data are presented