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