Reconstructing a three-dimensional model with arbitrary errors
Reconstructing a three-dimensional model with arbitrary errors
复制标题
DOI：
10.1145/301970.301972
复制
发表时间：
1999-03-01
影响因子：
2.5
通讯作者：
Leighton, T
中科院分区：
文献类型：
--
作者：
Berger, B;Kleinberg, J;Leighton, T
目前的一些技术可以确定蛋白质和RNA等结构中的原子间距离信息。因此，使用关于点间距离的信息重建三维点集已经成为确定分子结构的基本重要任务。从诸如NMR的技术获得的距离测量通常是稀疏的并且容易出错，这极大地使重建任务复杂化。这些误差中的许多导致距离测量，可以安全地假设位于某些固定公差内。但是，这些实验中的一些系统误差来源导致了很难量化的数据不准确;实际上，必须将测量距离矩阵的某些条目视为任意“损坏”。任意错误的存在导致了一种有趣的纠错问题-距离矩阵中有多少损坏的条目可以有效地纠正，以产生一致的三维结构？对于一个n × n矩阵的情况下，其中每一个条目都是指定的，我们提供了一个随机算法运行时间O（n log n），枚举所有结构符合最多（1/2 -n）n错误每行，具有很高的概率。在随机定位错误的情况下，我们可以纠正稀疏矩阵中相同密度的错误-其中每行中的条目仅给出beta分数，对于任何常数beta > 0。
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 three-dimensional 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 error-prone, 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 error-correction problem-how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? For the case of an n x 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 - epsilon)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 matrix-one in which only a beta fraction of the entries in each row are given, for any constant beta > 0.