Combinatorial classification to separate homogeneous subsets of heterogeneous projection sets.
Item
-
Title
-
Combinatorial classification to separate homogeneous subsets of heterogeneous projection sets.
-
Identifier
-
AAI3284420
-
identifier
-
3284420
-
Creator
-
Kalinowski, Miroslaw.
-
Contributor
-
Adviser: Gabor T. Herman
-
Date
-
2007
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
Some important image classification problems cannot be solved using standard techniques. The problem of classification of heterogeneous electron microscopic projections into homogeneous subsets, found in three-dimensional electron microscopy (3D-EM), belongs to this category. One important 3D-EM technique (the so-called single particle reconstruction) used to visualize complex 3D molecular structures relies on the assumption that thousands of projections of identical specimens are available. However, it is often the case that the macromolecule of interest appears in the projection set in several (not-exactly identical) conformations. The single particle method applied to such heterogeneous sets is unable to provide useful information about the encountered conformational diversity and produces reconstructions with severely reduced resolution. This limitation is a significant stumbling block to understanding molecular function (especially its dynamic aspects). One approach to solving this problem is to partition heterogeneous projection set into homogeneous components and apply existing reconstruction techniques to each of them. Due to the nature of the projection images and the high noise level present in them, this classification task constitutes a challenging computer science problem. A method is presented to achieve the desired classification by using a novel image dissimilarity measure and finding an approximate Max k-Cut of an appropriately constructed weighted graph. Despite of the large size (thousands of nodes) of the graph and the theoretical computational complexity of finding even an approximate Max k-Cut, we propose an algorithm that finds a good (from the perspective of 3D-EM projection image classification) approximate solution within several minutes (running on a standard PC). Due to the large number of edges the task of constructing the complete weighted graph (that represents an instance of the projection image classification problems) is computationally expensive. To reduce this cost we also propose a method, which utilizes an early-termination technique, to significantly reduce the computational cost of constructing such graphs. Unlike the majority of competing approaches, the presented method employs unsupervised classification (it does not require any prior knowledge about the objects being classified) and does not involve a 3D reconstruction procedure. The performance of the proposed classification method is evaluated on synthetically generated data sets produced by projecting 3D objects that resemble biological structures.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
