《蛋白质冷冻电镜图像的分类算法论文大学论文.doc》由会员分享，可在线阅读，更多相关《蛋白质冷冻电镜图像的分类算法论文大学论文.doc（20页珍藏版）》请在金锄头文库上搜索。
1、论文蛋白质冷冻电镜图像的分类算法研究Classification of Protein Cryo-EM Images 蛋白质冷冻电镜图像的分类算法研究摘要本篇论文的主要工作是对模拟的蛋白质二维投影图像进行分类。这个课题源于冷冻电镜蛋白质的三维重构，对蛋白质投影图像的分类平均是蛋白质三维重构的重要前提。我们首先根据蛋白质冷冻电镜图像的形成原理，模拟产生不同投影角度的蛋白质二维图像。然后提取图像的平移旋转不变量，为之后的分类做准备。由于模拟产生的图像中蛋白质的投影图像都是居中的，所以可近似忽略其平移变量。旋转不变量是通过对图像做极坐标变换和傅里叶变换而提取到的。接着运用k-medoids算法,一种
2、典型的基于划分的聚类方法,对处理后的图像进行分类。最后采用了由Fowlkes和Mallows提出的一种评估聚类结果的方法，用来验证本课题的分类结果。在结果分析中，我们给输入图像分别加入不同的高斯白噪声，然后对比不同信噪比图片的聚类结果，得出该算法能够处理的信噪比的范围。此外，我们还对比了在输入图像总数不同或类别数不同时的分类结果。以此来全面评估k-medoids算法对蛋白质投影图像的分类效果。关键词：蛋白质，图像，分类，旋转不变性，k-medoids算法CLASSIFICATION OF PROTEIN CRYO-EM IMAGES AbstractIn this paper our main
3、 work is to classify simulated protein two-dimensional projection images. This problem is related with three-dimensional reconstruction of protein structure from cryo-EM data, the process of classification and averaging of the projected image is an important prerequisite for three-dimensional recons
4、truction of protein. First, we produce simulated projection images of protein from various directions, in accordance with the actual collection of cryo-EM images . Then extract the translation and rotation invariant from these images, to be used as features for the following classification. The proj
5、ected images are centered when we produce simulation images, so it can be approximated by ignoring its translational variables. We use the polar coordinate transformation and Fourier transform to obtain rotational invariances of images. Next use classical clustering methods, namely k-medoids algorit
6、hm, to classify the images. Finally, in order to assess the quality of the classification results, we use the index proposed by the Fowlkes and Mallows. In the experiments, we added different Gaussian white noise to the input image, and compared the results of clustering with different signal to noi
7、se ratio,. In order to fully assess the k-medoids algorithm for projected image classification, we also assessed the quality of the classification by comparing the results of different number of input images and different number of clasters. Keywords: protein, images, classification, rotational inva
8、riance, k-medoids algorithm目录蛋白质冷冻电镜图像的分类算法研究I摘要IAbstractII目录III第1章绪论11.1 课题背景和意义11.2 国内外研究现状11.3 论文组织结构2第2章 聚类32.1 聚类的定义32.1.1 聚类定义32.1.2 相似性度量32.2 聚类的步骤42.3 聚类算法的分类42.3.1 基于层次的方法42.3.2 基于分割的方法52.3.3 基于密度的方法52.3.4 基于网格的方法52.3.5 基于模型的方法52.4 小结5第3章 k-medoids 算法63.1 k-medoids 算法的基本原理63.2 k-medoids 算法的
9、流程6第4章 对蛋白质冷冻电镜下图像的分类处理84.1 模拟产生蛋白质冷冻电镜下的图像84.2 对冷冻电镜下蛋白质图片的分类84.2.1 提取特征8 4.2.2 相似性度量104.2.3 k-medoids 算法聚类过程104.3 对聚类结果的分析评估10第五章 总结与展望13IV毕业论文 蛋白质冷冻电镜图像的分类算法研究第1章绪论1.1 课题背景和意义蛋白质作为生命体的主要组成成分，生命活动的主要执行者，是生物有机体生命现象的直接体现者，而仅凭目前已知的蛋白质根本无法阐明各种复杂的生命活动过程。而以蛋白质为主体的生物大分子的功能主要取决于它们的三维结构。因此，研究蛋白质结构对于了解各种蛋白质
10、的性质和功能就非常重要。研究蛋白质结构的方法主要有三种：X射线晶体学(X-ray)、核磁共振技术(NMR)和冷冻电子显微镜(Cryo-EM)。目前，由于前两种技术具有不易测定大分子复合物结构等局限性，冷冻电镜三维重构已经成为研究生物大分子结构和功能的强有力手段。冷冻电镜三维重构首先利用快速冷冻技术对蛋白质样品进行冷冻固定，然后利用冷冻电镜对样品进行电子成像，接着将底片数字化，对数字化的图像进行二维图像分析选点、分类、校正和平均，最后完成该蛋白质的三维重构1。由于蛋白质结构的整个三维重构过程极其复杂且会耗费大量的时间，本课题就截取过程中的关键步骤，即二维图像的分类过程。我们期望改进图像的分类算法
11、，以取得良好的分类效果，致使下一步三维重构时，能够提高重构模型的正确性，并降低蛋白质三维重构的难度，减少重构消耗的时间。1.2 国内外研究现状目前，对于单粒子重构过程中的二维图像分类平均，主要有两种方法，IMAGIC和SPIDER。IMAGIC使用多元变量统计分析法(MSA)和多参考对准法(MRA)进行二维图像分类、平均。MSA先对较大的图像集进行压缩和去噪，然后用基于分层的分类方法对图像集进行高效的分类。聚类后的图像为MRA进行类平均操作提供参考。因为原本是同一角度的投影图像，有时只是经过了小幅度的平移和旋转，所以为了实现不同角度的投影图像的分类，我们需要预先提取一些不变特征，例如，用自相关
12、函数(ACF)或双自相关函数(DACF)进行提取。SPIDER先用无参考对准法(RFA)，接着用旋转不变特征向量作为K-means聚类的输入，对二维图像分类。RFA试着在全局范围内去对准图像。这种优化方法主要是在所有图像与其平均值的偏差平方总和最小(即最小方差)时，找到它们的旋转和变换的对准参数11。另外，如今很多三维重构的软件中也包含二维图像的分类平均过程，不同的软件采用了各种不同的算法。二维图像分类平均过程大部分采用RFA，但是当图像来自大量不同角度的投影时，该方法就会出错。而且如果要实现全局对准，这样就需要所有图片两两比较一次，对准就需要n(n-1)/2次操作。这种操作耗时且没必要，因为
13、大部分时间都用在完全不同的图片的对准上了11。1.3 论文组织结构 本课题主要模拟蛋白质冷冻电镜图像三维重构中的二维图像的分类过程。采用了聚类中的k-medoids算法，对图像分类，并分析了该算法的分类效果，统计评估了分类结果。本文各章安排如下：第一章 为绪论，简要介绍了蛋白质冷冻电镜下三维重构的背景，并说明了选题的意义。接着还详述了现如今二维图像分类平均过程在国内外的研究现状。第二章 介绍了聚类的相关概念及其分类。第三章 介绍了k-medoids 算法的基本原理。第四章 介绍对蛋白质冷冻电镜下图像的整个处理过程，阐述了整个过程的步骤以及相关的原理。第五章 为总结与展望。第2章 聚类2.1 聚
14、类的定义2.1.1 聚类定义 聚类是根据所提取的样本特征的相似性，将输入的数据集划分为几种不同的子数据集，分类的结果是使得同一类中的数据相似度较高，而不同类间的数据差别较大。特征提取就是将样本数据转化为若干个特征的过程。从数学上讲，特征提取相当于把一个物理模式变为一个随机向量。提取的特征必须能够唯一标识该样本，且一般具有伸缩、旋转、平移不变性。数据间的相似性一般用最短距离或相似系数来度量。 聚类与分类不同。聚类属于无监督式学习，即开始对数据集分类时，并没有数据相关的类信息，只是从所有数据中随机选取样本作为类参考，然后根据相似性度量规则将数据划分入各个类中。相反，分类属于监督式学习，分类模型中存
15、在数据样本，且这些数据的类标号已知，分类就是从训练样本集中提取出分类的规则，用于标识其他类标号未知的数据。2.1.2 相似性度量正如2.1.1中所述，聚类的依据是数据间的相似性，即从样本中所提取的特征的相似程度。通常描述样本相似性的方法主要有两种：距离和相似系数。(1) 距离：假设用n个特征变量来描述样本，那么该样本X即为n维特征向量，这样我们就可以将样本看成n维欧式空间中的一个点，然后选用某种距离公式，求与其他各点间的距离。距离越小，则表示两样本间相似性越高，反之，则越低。一般采用欧几里得距离作为相似性度量。(2) 相关系数：这是衡量两个随机变量间线性相关程度的指标。X、Y表示两个样本，其相似性计算公式如下：若两个变量的相关系数越接近1，则表明它们越相似；反之，越接近0，则差异越大。2.2 聚类的步骤(1) 特征提取。这一步的输入是原始样本数据，然后根据具体情况决定提取哪些特征来刻画样本的属性和结构。特征提取的输出是一个向量或矩阵。有时，提取的特征变量过多，不利于后续的分析处理，这时可以进行降维处理，降低空间维数，方便运算。另外，提取的特征变量之间，必须是相互独立的，所以可用主成成分分析法消除特征变量间的相关性
