Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. The Molecule Problem: Determining Conformation from Pairwise Distances

The Molecule Problem: Determining Conformation from Pairwise Distances

File(s)
90-1159.pdf (9.76 MB)
90-1159.ps (1.6 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6999
Collections
Computer Science Technical Reports
Author
Hendrickson, Bruce A.
Abstract

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.

Date Issued
1990-09
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1159
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance