ICS Theory Group

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.)