A fast calculation strategy of density function in ISAF reconstruction algorithm

Abstract

The ISAF reconstruction algorithm is a new method for reconstructing icosahedral molecules from their projections. This algorithm works in spherical coordinate system and can achieve higher resolution than the traditional Fourier-Bessel algorithm in cylindrical coordinate system; however this method needs huge computations, which limits its application in reality. The main bottleneck lies in the calculation of density function as it occupies 90% running time of the whole algorithm. A fast calculation strategy of density function is proposed to solve this problem. This strategy is composed of three components: the fast calculation method of density function of mesh point in spherical coordinate system, the transformation method of density function of mesh point from spherical coordinate system to Cartesian coordinate system and the fast two-phase mapping method. The time complexity of calculating density function is decreased from O[(LM)8] to O[(LM)7] in our strategy. The experimental results on Psv-F simulated data indicate that the speed of calculating density function is increased almost two orders of magnitude and the speedup of the whole algorithm could reach 30 times. In addition, the speedup could go up with the increase in the number of images and the requirement of accuracy. © 2012 Science China Press and Springer-Verlag Berlin Heidelberg.