ICS 269, Fall 1996: Theory Seminar
6 Dec 1996:
Reconstructing a Three-Dimensional Model with Arbitrary Errors
Thuan Do, ICS, UC
Irvine
A number of current technologies allow for the determination of
inter-atomic distance information in structures such as proteins
and RNA. 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 determining molecular structure. But
the measurements are error-prone and some of the entries of the
mesured distance matrix are arbitrarity "corrupted."
In this paper, the authors present an algorithm which runs in
O(n log n) time, where n is the
number of points, and that algorithm can reconstruct the model of
points P from its distance matrix, which has many errors and
which is also not complete. The algorithm will produce a constant
number of point sets consistent to a given distance matrix
M, and one of them will be the correct point set P.
(Based on a STOC '96 paper by Bonnie Berger, Jon
Kleinberg, and Tom
Leighton.)