Journal of Computers, Vol 7, No 2 (2012), 528-533, Feb 2012
doi:10.4304/jcp.7.2.528-533

An Accelerated ISAF Algorithm with the Fast Mapping Strategy

Gongming Wang, Fa Zhang, Fei Sun, Zhiyong Liu

Abstract


ISAF (icosahedral symmetry-adapted functions) is a new approach used for 3D reconstruction of icosahedral macromolecules, which can achieve better resolutions compared with the commonly used Fourier-Bessel algorithm. However, ISAF is significantly slow. Among all reasons, the operation that rotating each image sixty times costs lots of running time. By analyzing the sixty symmetrical characteristics of icosahedrons in Fourier space, we proved that the positions of sixty mapped points derived from one sampling point are all the same in asymmetric unit. Thus, the sixty symmetrical rotating of each image can be removed and the reconstruction speed is increased. This accelerating strategy was validated by means of experiments with simulated data and experimental Cryo-EM data. The results showed that the speedup of this strategy was up to 41 times and it could grow up with the increase of the maximum Fourier radius and the number of images at the premise of maintenance of accuracy. Its running speed is about 9 times as great as that of Fourier-Bessel algorithm and is about 3 times than that of recISAFs algorithm.


Keywords


3D reconstruction; mapping; asymmetric unit; ISAF; speedup

References


[1] DeRosier D J,Klug A: Reconstruction of three-dimensional structures from electron micrographs. Nature(London)1968, 217:130-134.
http://dx.doi.org/10.1038/217130a0

[2] Bottcher B, Wynne S A, Crowther R A: Determination of the fold of the core protein of hepatitis B virus by electron cryomicroscopy. Nature 1997, 386:88-91.
http://dx.doi.org/10.1038/386088a0
PMid:9052786

[3] Conway J F, Cheng N, Zlotnick A,Wingfield P T, Stahl S J, Steven A C: Visualization of a 4-helix bundle in the hepatitis B virus capsid by cryo-electron microscopy. Nature 1997, 386:91-94.
http://dx.doi.org/10.1038/386091a0
PMid:9052787

[4] Caspar D L D, Klug A: Physical Principles in the Construction of Regular Viruses. Cold Spring Harbor Symposia on Quantitative Biology 1962, 27:1-24.
http://dx.doi.org/10.1101/SQB.1962.027.001.005
PMid:14019094

[5] Z Hong Zhou: Towards atomic resolution structural determination by single particle cryo-electron microscopy. Current Opinion in Structural Biology 2008, 18(2):218–228.
http://dx.doi.org/10.1016/j.sbi.2008.03.004
PMid:18403197    PMCid:2714865

[6] Hongrong Liu, Lingpeng Cheng, et al: Symmetry-adapted spherical harmonics method for high-resolution 3D single-particle reconstructions. Journal of Structural Biology 2008, 161(1): 64-73.
http://dx.doi.org/10.1016/j.jsb.2007.09.016

[7] Gongming Wang, Fa Zhang, Qi Chu, Liya Fan, Fei Sun, Zhiyong Liu. A Fast Calculation Strategy of Density Function in ISAF Reconstruction Algorithm. SCIENCE CHINA, F Series. (Accepted)

[8] Xuekui Yu, Lei Jin1, Z. Hong Zhou; 3.88 Åstructure of cytoplasmic polyhedrosis virus by cryo-electron microscopy; Nature 453, 415-419 (15 May 2008)
http://dx.doi.org/10.1038/nature06893
PMid:18449192    PMCid:2746981

[9] Zhou Z H, Dougherty M, Jakana J, He J, Rixon F J, Chiu W. 2000. Seeing the herpesvirus capsid at 8.5 Å. Science 2000, 288(5467):877–880.
http://dx.doi.org/10.1126/science.288.5467.877
PMid:10797014

[10] Gabashvili I S, Agrawal R K, Spahn C M, Grassucci R A, Svergun D I, Frank J, Penczek P. Solution structure of the E. coli 70S ribosome at 11.5 Å. Cell 2000, 100(5):537–549.
http://dx.doi.org/10.1016/S0092-8674(00)80690-X

[11] Wada Y, Tanaka H, et al. The structure of melon necrotic spot virus determined at 2.8 A resolution. Acta Crystallogr,Sect.F 2008, 64:8-13.
http://dx.doi.org/10.1107/S1744309107066481
PMid:18097092    PMCid:2374003

[12] Ludtke, S.J., Baldwin, P.R., Chiu, W., 1999. EMAN: semi-automated software for high resolution single particle reconstructions. J. Struct. Biol. 128, 82–97.
http://dx.doi.org/10.1006/jsbi.1999.4174
PMid:10600563

[13] Liang, Y., Ke, E.Y., Zhou, Z.H., 2002. IMIRS: a high-resolution 3D reconstruction package integrated with a relational image database. J. Struct. Biol. 137, 292–304.
http://dx.doi.org/10.1016/S1047-8477(02)00014-X

[14] Harauz G., Van Heel M:Exact filters for general geometry three dimensional reconstruction. Optik 1986, 73:146–156.

[15] Penczek P A, Zhu J, Schroder R, Frank J. Three-dimensional reconstruction with contrast transfer compensation from defocus series. Scanning Microscopy 1997, 11:147-154.


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.