A fast hermite transform with applications to protein structure determination

ABSTRACT

We discuss algorithms for a fast and stable approximation of the Hermite transform of a compactly supported function on the real line, attainable via an application of a fast algebraic algorithm for computing sums associated to a three-term relation. Trade-offs between approximation in bandwidth (in the Hermite sense) and size of the support region are addressed. Generalizations to any family of orthogonal polynomials are outlined. Applications to the determination of protein structure are discussed.

REFERENCES

• 1: T. S. Baker and R. H. Cheng. A model-based approach for determining orientations of biological macromolecules imaged by cryoelectron microscopy. J. Struct. Biol., 116:120--130, 1996.
• 2: H. Bateman. Higher Transcendental Functions, Vol. 2. McGraw-Hill (California Institute of Technology: Bateman Manuscript Project), New York, 1953.
• 3: A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860870]
• 4: R. Bulirsch and J. Stoer. Introduction to Numerical Analysis. Springer-Verlag, Berlin, 2002.
• 5: P. Burgisser, M. Clausen, , and M. A. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag, Berlin, 1996.
• 6: P. C. Doerschuk and J. E. Johnson. Ab initio reconstruction and experimental design for cryo electron microscopy. IEEE Trans. Information Theory, 46(5):1714--1729, 2000.
• 7: J. R. Driscoll , D. M. Healy, Jr. , D. N. Rockmore, Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs, SIAM Journal on Computing, v.26 n.4, p.1066-1099, Aug. 1997 [doi>10.1137/S0097539792240121]
• 8: H. P. Erickson. The fourier transform of an electron micrograph - first order and second order theory of image formation. In Advances in Optical and Electron Microscopy (R. Barer and V.E., Cosslett, eds.), pages 163--199. Academic Press, 1973.
• 9: J. Frank. Three-dimensional electron microscopy of macromolecular assemblies. Academic Press, San Diego, CA, 1996.
• 10: T. A. Jones, J.-Y. Zou, S. W. Cowan, and M. Kjeldgaard. Improved methods for building protein models in electron density maps and the location of errors in these models. Acta Crystallogr. A, 47:110--119, 1991.
• 11: Principles of computerized tomographic imaging, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 12: D. Kortchagine and A. Krylov. Hermite foveation. In Proceedings of Graphicon 2004, pages 166--169. Moscow, 2004.
• 13: D. Kortchagine and A. Krylov. Image database retrieval by fast Hermite projection method. In Proceedings of Graphicon 2005. Moscow, 2005.
• 14: I. Krasikov. New bounds on the Hermite polynomials. http://front.math.ucdavis.edu/math.CA/0401310, 2005.
• 15: J.-B. Martens. The Hermite transform -- Applications. IEEE Trans. Acoustics, Speech, Signal Processing, 38:1607--1618, 1990.
• 16: J.-B. Martens. The Hermite transform -- Theory. IEEE Trans. Acoustics, Speech, Signal Processing, 38:1595--1606, 1990.
• 17: M. Najafi, A. Krylov, and D. Kortchagine. Image deblocking with 2-D Hermite transform. In Proceedings of Graphicon 2003, pages 180--183. Moscow, 2003.
• 18: T. J. Oldfield. High-resolution crystallographic map interpretation. Acta Crystallographica Section D-Biological Crystallography, 58:963--967, 2002.
• 19: W. Park and G. S. Chirikjian. Tomographic reconstruction using band-limited Hermite expansions. in preparartion, 2006.
• 20: W. Park and G. S. Chirikjian. Lossless image rotation using band-limited Hermite expansions. in review, 2006.
• 21: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 22: O. Scherzer. The theoretical resolution limit of the electron microscope. J. Appl. Phys., 20:20-29, January 1949.
• 23: G. Szegö. Orthogonal Polynomials. Amer. Math. Soc. Colloq. Publ. 23, Providence, RI, 1975.
• 24: M. van Heel. Imagic and its results. Ultramicroscopy, 4:117, 1979.
• 25: M. van Heel, G. Harauz, , and E. V. Orlova. A new generation of the imagic image processing system. J. Struct. Biol, 116:17--24, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
generalized fourier transform, hermite transform, orthogonal polynomial transform, three-term recurrence