Reconstructing a three-dimensional model with arbitrary errors

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-&egr;)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 &bgr; fraction of the entries in each row are given, for any constant &bgr;gt;0.

REFERENCES

• 1: BOLKER, E. D., AND ROTH, B. 1980. When is a bipartite graph a rigid framework? Pacific J. Math. 90, 27-44.
• 2: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• 3: CAUCHY, A.L. 1813. Sur les polygones et poly6dres. J. E, cole Polytech. 19 87-90.
• 4: 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.
• 5: CRIPPEN, G. M., AND HAVEL, T.F. 1988. Distance Geometry and Molecular Conformation. Wiley, New York.
• 6: Andreas W. M. Dress , Timothy F. Havel, Shortest-path problems and molecular conformation, Discrete Applied Mathematics, v.19 n.1-3, p.129-144, March 1988 [doi>10.1016/0166-218X(88)90009-1 ]
• 7: Andreas W. M. Dress , Timothy F. Havel, Bound smoothing under chirality constraints, SIAM Journal on Discrete Mathematics, v.4 n.4, p.535-549, Nov. 1991 [doi>10.1137/0404047]
• 8: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 9: Bruce Alan Hendrickson, The molecule problem: determining conformation from pairwise distances, Cornell University, Ithaca, NY, 1991
• 10: HENNENBERG, L. 1911. Die graphische Statik der starren Systeme. Leipzig.
• 11: KOLATA, G. 1978. Geodesy: Dealing with an enormous computer task. Science 200 421-422.
• 12: LANE, A., AND FULCHER, T. 1995. aH NMR relaxation and NOE's in nucleic acids. J. Magn. Res. 107, 34-42.
• 13: MILNOR, J. 1964. On the Betti numbers of real varieties. Proc. AMS 15, 275-280.
• 14: NI, F. 1995. Two-dimensional transferred NOE effects with incomplete averaging of free- and bound-ligand resonances. J. Magn. Res. 106, 147-155.
• 15: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 16: 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.
• 17: 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.
• 18: 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.
• 19: WHITELEY, W. 1984. Motions of a bipartite framework. Pacific J. Math. 110, 233-255.
• 20: 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.
• 21: WUYDEaLICH, W. 1977. Untersuchungen zu einem trilaterations mit komplanaren standpunkten. Sitz. Osten. Akad. Wiss. 186, 263-280.
• 22: WUTHRICH, K. 1986. NMR of Proteins and Nucleic Acids. Wiley, New York.
• 23: ZHU, L., AND REID, B. 1995. An improved NOESY simulation program for partially relaxed spectra: BIRDER, J. Magn. Res. 106, 227-235.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Chemistry
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory

Keywords:
biomolecular structure, distance geometry, random sampling, randomized algorithms