ISAF重构算法密度函数快速计算模型

A fast calculation strategy of density function in ISAF reconstruction algorithm

球坐标系下的ISAF算法是一种新的20面体分子三维重构方法,该方法精度优于传统柱坐标系下的Fourier-Beseel算法,但其执行速度远低于Fourier-Bessel算法,严重制约了ISAF算法的实际应用.分析发现,在ISAF算法中密度函数计算是影响重构速度的主要瓶颈之一.针对上述问题,文中提出一种密度函数快速计算模型,该模型包括三个组成部分:球坐标系网格点密度函数快速计算方法、"球坐标系—直角坐标系"网格点密度函数转换方法、基于两阶段映射法的快速对称映射方法.该模型可以将密度函数计算阶段的时间复杂度由O[(LM)8]降低到O[(LM)7].采用Psv-F病毒数据进行实验,结果表明,在保证精度的前提下,该模型可以将密度函数的计算速度提高2个数量级,将三维重构整体速度提高30倍左右,并且随着数据规模的增大、重构精度的提高,该模型带来的加速比将进一步增大.

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.