


Reconstructing a ThreeDimensional Model with Arbitrary Errors


Bonnie Berger, Jon Kleinberg, and Tom Leighton




A number of current technologies allow for the determination of
interatomic distance information in structures such as proteins and
RNA. Thus, the reconstruction of a threedimensional set of points
using information about its interpoint distances has become a task of
basic importance in determining molecular structure. The distance
measurements one obtains from techniques such as NMR are typically
sparse and errorprone, greatly complicating the reconstruction
task. Many of these errors result in distance measurements that can be
safely assumed to lie within certain fixed tolerances. But a number of
sources of systematic error in these experiments lead to inaccuracies
in the data that are very hard to quantify; in effect, one must treat
certain entries of the measured distance matrix as being arbitrarily
"corrupted."
The existence of arbitrary errors leads to an interesting sort of
errorcorrection problem  how many corrupted entries in a distance
matrix can be efficiently corrected to produce a consistent
threedimensional structure? For the case of an n × n matrix in which
every entry is specified, we provide a randomized algorithm running in
time O(n log n) that enumerates all structures consistent with at most
(1/2  )n errors per row, with high probability. In
the case of randomly located errors, we can correct errors of the same
density in a sparse matrixone in which only a fraction
of the entries in each row are given, for any constant
> 0.


http://delivery.acm.org/10.1145/310000/301972/p212berger.pdf



