Bonnie Berger
Jon Kleinberg
Abstract
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 × 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 matrix-one in which only a β fraction of the entries in each row are given, for any constant βgt;0.
- BOLKER, E. D., AND ROTH, B. 1980. When is a bipartite graph a rigid framework? Pacific J. Math. 90, 27-44.Google Scholar
- BOLLOBAS, B. 1978. Extremal Graph Theory. Academic Press, Orlando, Fla. Google Scholar
- CAUCHY, A.L. 1813. Sur les polygones et poly6dres. J. E, cole Polytech. 19 87-90.Google Scholar
- COYYELLY, R. 1991. On generic global rigidity. In Applied Geometry and Discrete Mathematics, DIMACS Series, vol. 4. P. Gritzmann, B. Sturmfels et al., eds. American Mathematics Society, Providence, R.I., pp. 147-155.Google Scholar
- CRIPPEN, G. M., AND HAVEL, T.F. 1988. Distance Geometry and Molecular Conformation. Wiley, New York.Google Scholar
- DRESS, A., AND HAVEL, T. F. 1988. Shortest-path problems and molecular conformation. Disc. Appl. Math. 19, 129-144. Google Scholar
- DRESS, A., AND HAVEL, T.F. 1991. Bound smoothing under chirality constraints. SIAM J. Disc. Math. 4 535-549. Google Scholar
- HENDRICKSON, B. 1992. Conditions for unique graph realizations. SIAM J. Comput. 21, 65-84. Google Scholar
- HENDRICKSON, B. 1990. The molecule problem: Determining conformation from pairwise distances. Ph.D. dissertation. Dept. of Computer Science, Cornell Univ., Ithaca, N.Y. Google Scholar
- HENNENBERG, L. 1911. Die graphische Statik der starren Systeme. Leipzig.Google Scholar
- KOLATA, G. 1978. Geodesy: Dealing with an enormous computer task. Science 200 421-422.Google Scholar
- LANE, A., AND FULCHER, T. 1995. aH NMR relaxation and NOE's in nucleic acids. J. Magn. Res. 107, 34-42.Google Scholar
- MILNOR, J. 1964. On the Betti numbers of real varieties. Proc. AMS 15, 275-280.Google Scholar
- NI, F. 1995. Two-dimensional transferred NOE effects with incomplete averaging of free- and bound-ligand resonances. J. Magn. Res. 106, 147-155.Google Scholar
- RAGHAVAN, P. 1988. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 37, 130-143. Google Scholar
- SAXE, J. 1979. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 19th Allerton Conference on Computers, Controls, and Communications. pp. 480-489.Google Scholar
- THOM, R. 1965. Sur l'homologie des vari6t6s alg6briques r6elles. In Differential and Combinatorial Topology, S. S. Cairns, ed. Princeton University Press, Princeton, N.J.Google Scholar
- WANG, A., KIM, S., FLYNN, P., CHOU, S., ORBAN, J., AND REID, B. 1992. Errors in RNA NOESY distance measurements in chimeric and hybrid duplexes: differences in RNA and DNA proton relaxation. Biochemistry 31, 3940-3946.Google Scholar
- WHITELEY, W. 1984. Motions of a bipartite framework. Pacific J. Math. 110, 233-255.Google Scholar
- WIDER, G., MACURA, S., KUMAR, A., ERNST, R., AND WUTHRICH, K. 1984. Homonuclear twodimensional 1H NMR of proteins. Experimental procedures. J. Magn. Res. 56, 207-234.Google Scholar
- WUYDEaLICH, W. 1977. Untersuchungen zu einem trilaterations mit komplanaren standpunkten. Sitz. Osten. Akad. Wiss. 186, 263-280.Google Scholar
- WUTHRICH, K. 1986. NMR of Proteins and Nucleic Acids. Wiley, New York.Google Scholar
- ZHU, L., AND REID, B. 1995. An improved NOESY simulation program for partially relaxed spectra: BIRDER, J. Magn. Res. 106, 227-235.Google Scholar
Index Terms
- Reconstructing a three-dimensional model with arbitrary errors
Recommendations
Exterminator: automatically correcting memory errors with high probability
PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and ImplementationPrograms written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, whichcan lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down ...
Exterminator: automatically correcting memory errors with high probability
Proceedings of the 2007 PLDI conferencePrograms written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, whichcan lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down ...
Advances on the Geometric Algebra approach to the Discretizable Molecular Distance Geometry Problem (DMDGP)
CGI '16: Proceedings of the 33rd Computer Graphics InternationalWe consider the Discretizable Molecular Distance Geometry Problem (DMDGP), which is a subclass of the Distance Geometry Problem (DGP), where the search space can be discretized. The DMDGP consists in finding a 3D protein structure for which some of the ...
Comments