We will focus primarily on an application of combinatorial optimization to some geometric problems that arise in the analysis of molecular structure. A number of current technologies such as nuclear magnetic resonance make possible the determination of inter-atomic distances in organic molecules. Thus, the reconstruction of a three-dimensional set of points using information about its inter-point distances has become a task of basic importance in studying molecular conformation. However, the distance data one obtains from techniques such as NMR is typically sparse and error-prone, and many of the sources of systematic error lead to inaccuracies that are very hard to quantify. In effect, one must treat certain entries of the measured distance matrix as being arbitrarily "corrupted."
We present efficient algorithms for reconstructing sets of points in the presence of arbitrary errors in their inter-point distance data. Our algorithms can be viewed as addressing a basic error-correction problem in the geometric setting -- how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? We show that our algorithms work efficiently up to a natural "information-theoretic" limit -- a proportion of errors beyond which there are an infinite number of consistent three-dimensional structures.
Host: Prof. Nancy Lynch
|
Modified: Jun 25, 1997|
Current events|
Your comments
and inquiries are welcome.