ISAF重构算法基函数复杂性分析及解决方案

Analysis and Solution of Complexity of Basis Function in ISAF Reconstruction Algorithm

ISAF重构算法用于重建分子三维结构,其精度优于传统傅里叶-贝赛尔重构算法,但是复杂的基函数导致其速度很慢,严重影响该方法的推广应用,所以降低基函数复杂性十分重要.通过对ISAF重构算法基函数的复杂性进行分析,提出对应的解决方案.首先采用自然对数解决组合系数生成过程中的大数运算问题;然后为内存中的所有组合系数建立二级索引,提高其寻址速度,并且根据内存访问局部性原理把可能要用到的组合系数调入高速缓存,尽可能减少内存调入调出次数,提高访存速度;最后采用动态规划提高球谐函数计算速度,可以一次生成所有阶、所有次的球谐函数.将上述解决方案综合在一起,构建了一个基函数ISAF快速计算模型.为了验证该模型效果,采用戊肝病毒的模拟数据进行三维重构实验,并且与傅里叶-贝赛尔重构算法进行比较.实验结果表明,在不影响精度的前提下,采用该模型后ISAF重构算法的执行速度是傅里叶-贝赛尔重构算法的3倍左右,并且其加速效果随着图片数量的增加、分辨率要求的提高而增强.

ISAF reconstruction algorithm is used for reconstructing the three-dimensional structures of molecules.Its accuracy is better than that of traditional Fourier-Bessel reconstruction algorithm.But its basis function is so complex that lower its running speed particularly,which has affected the application of this method seriously.Therefore,it is very important to reduce the complexity of basis functions.By analyzing the complexity of the basis function,this paper proposed a solution.Firstly,the natural logarithm method is used for solving the large number computation problem in the course of generating combination coefficients.Secondly,a two-level index is built for all combination coefficients in memory to improve the addressing-speed.In addition,according to the locality principle during accessing memory,the combination coefficients that may be used in the near future are transferred into cache memory to reduce the number of accessing memory.Finally,the dynamic programming is used for improve the speed of computing spherical harmonic function,and the spherical harmonic function in all index and all times are computed at one pass.The fast computing model of ISAF basis function is built through an organic combination of the above methods.To validate this model,the simulated images of hepatitis E virus were used in three-dimensional reconstruction experiments.The referenced algorithm is the Fourier-Bessel reconstruction algorithm.The experiment results show that the running speed of ISAF reconstruction algorithm with this model is three times than that of Fourier-Bessel reconstruction algorithm.Furthermore,the speedup could grow up with the increase of the resolution requirement and the number of images.