University of Illinois Urbana-Champaign

Nearest neighbor search for cyro-electron microscopy images

Liu, Yang

Content Files
LIU-THESIS-2018.pdf

Permalink

https://hdl.handle.net/2142/101728

Description

Title
Nearest neighbor search for cyro-electron microscopy images
Author(s)
Liu, Yang
Issue Date
2018-07-19
Director of Research (if dissertation) or Advisor (if thesis)
Zhao, Zhizhen
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2018-09-27T16:34:23Z
Keyword(s)
  • k-nearest neighbors search
  • neural network
  • cryo-electron microscopy
Abstract
Cryo-electron microscopy (EM) technology enables researchers to determine the structure of a molecule at a much higher resolution than ever before. The single particle reconstruction (SPR) is one of the most widespread techniques used to reconstruct the 3D model of a molecule from its large set of cryo-EM projection images with unknown viewing angles. Classifying those projection images with similar views is regarded as one of the significant steps in the SPR problem. The goal in our research thesis is to find an effective way to identify and classify cryo-EM images solely based on their viewing angles. In the first part of the thesis, we try four different k-nearest neighbors search (KNNS) algorithms on cryo-EM projection images classifying them based on the viewing directions. Brute force search (BFS) could be very time consuming when the dataset is large. Therefore, strategies like locality sensitive hashing (LSH) and some neural network methods are taken into consideration. The LSH method maps similar items into the same cell in a hash table, which effectively shortens the query time of searching for k-nearest neighbors, while the neural network methods are able to capture more expressive features, and then the classification is performed according to these learned features. The four KNNS algorithms include hyperplane LSH, cross-polytope LSH, unsupervised stochastic generative hashing (SGH) as well as unsupervised deep hashing (DH). Their performances are analyzed by the accuracy for finding 100 near neighbors for each query data, construction time and query time. However, all four algorithms fail to accurately classify projection images under similar views because of the orientation difference. Thus, further preprocessing techniques are required. One of the techniques we take is augmenting the image dataset by generating more planar rotation copies for each projection image in a way that allows more image candidates under the same view observable. It shows that with image augmentation, the accuracies of all four methods increase. The LSH methods provide rather good performances both in computation time and the accuracy of searching for 100 nearest neighbors if the dataset is clean. However, for the noisy dataset, the traditional PCA is not working, and other preprocessing techniques should be applied to avoid color noise caused by the rotational image copies. In the second part of the thesis, we attempt to devise a neural network model for learning rotation invariant features of the cryo-EM images as well as reconstructing them from the invariant features. After obtaining the desired rotation-invariant features, we can use the LSH method to do the classification since the trained features are distinguished solely depending on the viewing direction. In addition, this model possibly could be used in recovering the 3D molecule structure directly from 2D projection images, which will be explained in details in Section 3.3.7. However, since the image is often of large size, this 3D model reconstruction could be a highly complex computation problem. Currently, we begin with building up a simple version of this model and test with 1D signals. It shows that this model works well for small-length signals. However, when the signal length gets larger, it becomes harder to optimize the model and the result is less satisfying. Therefore, in the future we may need to adjust the architecture of the neural network model and tune the hyper-parameters to make the model adapt to a more general case.
Graduation Semester
2018-08
Type of Resource
text
Permalink
http://hdl.handle.net/2142/101728
Copyright and License Information
Copyright 2018 Yang Liu

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois