Fast Alignment Algorithm for Cryo-EM Particle Images Based on Harmonic Analysis

Abstract

Cryo-electron microscopy (Cryo-EM) is a revolutionizing technique that facilitates the determination of macromolecule structures. To attain high-resolution structures, numerous noisy images should be iteratively aligned and reconstructed into 3D models. The alignment step is the bottleneck of computational efficiency in the existing frameworks. In this paper, we indicate the log-likelihood (LLH) function for alignment can be converted to a concise form through proper domain transformation. Based on this conversion and the corresponding fast transformation algorithms, a fast and precise alignment algorithm is proposed. The algorithm reduces the computational complexity from $\mathcal{O}({N^7})$ to $\mathcal{O}({N^5}\log N)$ (where N is the sample points in each dimension). The efficiency and correctness of the proposed algorithm are validated by the experiments on both synthetic and real datasets.