Representation theoretic patterns in three dimensional Cryo-Electron Microscopy I: The intrinsic reconstitution algorithm

Abstract

In this paper, we reveal the formal algebraic structure underlying the intrinsic reconstitution algorithm, introduced by Singer and Shkolnisky in [S], for determining three dimensional macromolecular structures from images obtained by an electron microscope. Inspecting this algebraic structure, we obtain a conceptual explanation for the admissibility (correctness) of the algorithm and a proof of its numerical stability. In addition, we explain how the various numerical observations reported in that work follow from basic representation theoretic principles.

  • [C] Go to document R. A. Crowther, DeRosier, D. J., and A. Klug, "The reconstruction of a three-dimensional structure from projections and its application to electron microscopy," Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 317, pp. 319-340, 1970.
    @article{C,
      author={Crowther, R. A. and DeRosier and D. J. and Klug, A.},
      TITLE={The reconstruction of a three-dimensional structure from projections and its application to electron microscopy},
      JOURNAL={Proc. R. Soc. Lond. {\rm A},
      Math. Phys. Sci.},
      VOLUME={317},
      YEAR={1970},
      PAGES={319-340},
      doi = {10.1098/rspa.1970.0119},
      }
  • [D] Go to document D. A. Doyle, J. M. Cabral, R. A. Pfuetzner, A. Kuo, J. M. Gulbis, S. L. Cohen, B. T. Chait, and R. MacKinnon, "The structure of the potassium channel: Molecular basis of K+ conduction and selectivity," Science, vol. 280, pp. 69-77, 1998.
    @article{D,
      author={Doyle, D. A. and Cabral, J. M. and Pfuetzner, R. A. and Kuo, A. and Gulbis, J. M. and Cohen, S. L. and Chait, B. T. and MacKinnon, R.},
      TITLE={The structure of the potassium channel: {M}olecular basis of {K}+ conduction and selectivity},
      JOURNAL={Science},
      VOLUME={280},
      PAGES={69--77},
      YEAR={1998},
      URL= {http://www.ncbi.nlm.nih.gov/pubmed/9525859},
      }
  • [F] J. Frank, "Three-Dimensional Electron Microscopy of Macromolecular Assemblies," in Visualization of Biological Molecules in Their Native State, Oxford: Oxford, 2006.
    @incollection{F,
      author={Frank, J.},
      TITLE={Three-Dimensional Electron Microscopy of Macromolecular Assemblies},
      BOOKTITLE={Visualization of Biological Molecules in Their Native State},
      PUBLISHER={Oxford},
      ADDRESS={Oxford},
      PAGES={},
      YEAR={2006},
      }
  • [G] A. Goncharov and B. Vainshtein, "Determination of the spatial orientation of arbitrarily arranged identical particles of an unknown structure from their projections," Proc. XI Internat. Congr. Elec. Micro., Kyoto, vol. I, pp. 459-460, 1986.
    @article{G,
      author={Goncharov, A. and Vainshtein, B.},
      TITLE={Determination of the spatial orientation of arbitrarily arranged identical particles of an unknown structure from their projections},
      JOURNAL={Proc. {\rm XI} Internat. Congr. Elec. Micro., Kyoto},
      VOLUME={I},
      PAGES={459--460},
      YEAR={1986},
      }
  • [HS] R. Hadani and A. Singer, Representation theoretic patterns in three dimensional cryo-electron macroscopy II – The class averaging problem.
    @misc{HS,
      author={Hadani, R. and Singer, A.},
      TITLE={Representation theoretic patterns in three dimensional cryo-electron macroscopy {II} - {T}he class averaging problem},
      NOTE={accepted for publication in {\it Foundations of Computational Mathematics (FoCM)},
      2011},
      }
  • [H] Go to document R. Henderson, "Realizing the potential of electron cryo-microscopy," Q. Rev. Biophys., vol. 37, pp. 3-13, 2004.
    @article{H,
      author={Henderson, R.},
      TITLE={Realizing the potential of electron cryo-microscopy},
      JOURNAL={Q. Rev. Biophys. },
      VOLUME={37},
      YEAR={2004},
      PAGES={3-13},
      NOTE={Review. PMID: 17390603 [PubMed - indexed for MEDLINE] },
      DOI={10.1017/S0033583504003920},
      }
  • [L] Go to document S. J. Ludtke, M. L. Baker, D. H. Chen, J. L. Song, D. T. Chuang, and W. Chiu, "De Novo backbone trace of GroEL from single particle electron cryomicroscopy," Structure, vol. 16, pp. 441-448, 2008.
    @article{L,
      author={Ludtke, S. J. and Baker, M. L. and Chen, D.H. and Song, J. L. and Chuang, D. T. and Chiu, W.},
      TITLE={De {N}ovo backbone trace of {G}ro{EL} from single particle electron cryomicroscopy},
      JOURNAL={Structure},
      VOLUME={16},
      YEAR={2008},
      PAGES={441-448},
      NOTE={PMID: 18334219 [PubMed - indexed for MEDLINE]},
      DOI={10.1016/j.str.2008.02.007},
      }
  • [M] Go to document R. MacKinnon, Potassium Channels and the Atomic Basis of Selective Ion Conduction, New York: Springer Science+Business Media, Inc., 2004, vol. 24.
    @book{M,
      author={MacKinnon, R.},
      TITLE={Potassium Channels and the Atomic Basis of Selective Ion Conduction},
      SERIES={Nobel Lecture, in Bioscience Reports},
      VOLUME={24},
      PUBLISHER={Springer Science+Business Media, Inc.},
      ADDRESS={New York},
      NOTE={PMID: 15628664 [PubMed - indexed for MEDLINE]},
      YEAR={2004},
      PAGES={75--100},
      DOI={10.1007/s10540-004-7190-2},
      }
  • [N] F. Natterer, The mathematics of computerized tomography, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2001.
    @book {N, MRKEY = {1847845},
      AUTHOR = {Natterer, F.},
      TITLE = {The mathematics of computerized tomography},
      SERIES = {Classics in Applied Mathematics},
      NUMBER = {32},
      PUBLISHER = {Society for Industrial and Applied Mathematics (SIAM)},
      ADDRESS = {Philadelphia, PA},
      YEAR = {2001},
      PAGES = {xviii+222},
      ISBN = {0-89871-493-1},
      MRCLASS = {00A69 (44A12 65R10 68U99 92C55)},
      MRNUMBER = {1847845},
      MRREVIEWER = {Fritz Keinert},
      ZBLNUMBER = {0973.92020},
      }
  • [S] A. Singer and Y. Shkolnisky, Three-dimensional Structure Determination From Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming, 2009.
    @misc{S,
      author={Singer, A. and Shkolnisky, Y.},
      TITLE={Three-dimensional Structure Determination From Common Lines in Cryo-{EM} by Eigenvectors and Semidefinite Programming},
      NOTE={submitted},
      YEAR={2009},
      }
  • [S2] A. Singer, Z. Zhao, , Y. Shkolnisky, and R. Hadani, "Viewing angle classification of Cryo-Electron Microscopy Images Using Eigenvectors," SIAM Journal on Imaging Sciences, vol. 4, pp. 723-759, 2011.
    @article{S2,
      author={Singer, A. and Zhao, Z. and and Shkolnisky, Y. and Hadani, R.},
      TITLE={Viewing angle classification of Cryo-Electron Microscopy Images Using Eigenvectors},
      JOURNAL={ SIAM Journal on Imaging Sciences},
      YEAR={ 2011},
      VOLUME={4},
      PAGES={723--759},
      }
  • [T] M. E. Taylor, Noncommutative Harmonic Analysis, Providence, RI: Amer. Math. Soc., 1986, vol. 22.
    @book {T, MRKEY = {0852988},
      AUTHOR = {Taylor, Michael E.},
      TITLE = {Noncommutative Harmonic Analysis},
      SERIES = {Math. Surveys and Monogr.},
      VOLUME = {22},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {1986},
      PAGES = {xvi+328},
      ISBN = {0-8218-1523-7},
      MRCLASS = {22E30 (43A65)},
      MRNUMBER = {0852988},
      MRREVIEWER = {L. Corwin},
      ZBLNUMBER = {0604.43001},
      }
  • [V] M. Van Heel, "Angular reconstitution: a posteriori assignment of projection directions for 3D reconstruction," Ultramicroscopy, vol. 21, pp. 111-123, 1987.
    @article{V,
      author={Van Heel, M.},
      TITLE={Angular reconstitution: a posteriori assignment of projection directions for 3{D} reconstruction},
      JOURNAL={Ultramicroscopy},
      VOLUME={21},
      YEAR={1987},
      PAGES={111--123},
      NOTE={PMID: 12425301 [PubMed - indexed for MEDLINE]},
      }
  • [W] L. Wang and F. J. Sigworth, "Cryo-EM and single particles," Physiology (Bethesda), vol. 21, pp. 13-8, 2006.
    @article{W,
      author={Wang, L. and Sigworth, F. J.},
      TITLE={Cryo-{EM} and single particles},
      JOURNAL={Physiology (Bethesda)},
      VOLUME={21},
      YEAR={2006},
      PAGES={13--8},
      NOTE={Review. PMID: 16443818 [PubMed -- indexed for MEDLINE]},
      }
  • [Z] Go to document X. Zhang, E. Settembre, C. Xu, P. R. Dormitzer, S. C. Harrison, and N. Grigorieff, "Near-atomic resolution using electron cryomicroscopy and single-particle reconstruction," Proc. Nat. Acad. Sci., vol. 105, pp. 1867-1872, 2008.
    @article{Z,
      author={Zhang, X. and Settembre, E. and Xu, C. and Dormitzer, P. R. and Harrison, S. C. and Grigorieff, N.},
      TITLE={Near-atomic resolution using electron cryomicroscopy and single-particle reconstruction},
      JOURNAL={Proc. Nat. Acad. Sci.},
      VOLUME={105},
      YEAR={2008},
      PAGES={1867-1872},
      DOI={10.1073/pnas.0711623105},
      }

Authors

Ronny Hadani

Department of Mathematics
The University of Texas at Austin
Austin, TX 78712

Amit Singer

Department of Mathematics and PACM
Princeton University
Princeton, NJ 08544