基因表达数据的双向聚类算法的研究

论文摘要

基因芯片的出现给生命科学研究、疾病诊断、新药开发、食品监督等领域带来了革命性的变化,而在一个典型的基因芯片的运作中,会有成千上万的基因表达数据产生,对基因表达数据的分析是当前生物信息学和数据挖掘领域的研究热点和难点。通常我们对基因表达数据的分析主要是通过使用聚类分析方法以找出基因表达数据矩阵中的显著性结构。由于基因表达数据的双向关联性（基因方向或条件方向）,传统聚类方法在分析中就显示出了局限性,它们因只在单方向上进行聚类故仅能找到整个数据集的全局结构信息,而大量的局部结构信息却被丢失掉了,但是具有生物学意义的显著性结构信息往往是内部局部相关联的,所以传统的聚类方法很难精确地反映出基因间的紧密关系。本文主要针对实数型数据与布尔型数据的基因表达中的双聚类问题进行了研究,具体做了以下一些工作：（1）提出了k-means迭代双聚类方法,此算法主要适应于实数集。使用了Cheng和Church算法中的平均平方残差作为打分函数,先进行列集聚类,再在聚类出来的列集上进行行聚类,然后列聚类与行聚类交叉迭代进行,以找出“稳态”双簇。第二步主要对“稳态”双簇进行降Hscore值（平均平方残差）,即为删行与删列操作。最后一步为最大化操作,即为加行与加列操作。实验表明：该算法可以同时挖掘出k个双聚类,而不像Cheng和Church算法每次只能挖掘出一个最大的双簇；且更能有效地找出变化较小,共表达水平较高的双聚类簇。此外,我们针对于无闭集双聚类（“稳态”双簇）也提出了一个算法,这个算法因其在列集上首先进行了聚类操作,把它划分成几个相似的子列集,再分别进行行聚类分析。该算法更适合挖掘出一些“瘦长”型的双聚类,双聚类的规模比上一个算法得到的更大型一些。（2）为了更加高效的处理基因表达谱,我们提出了处理布尔型数据的双向聚类算法。我们首先把布尔矩阵双向聚类问题转化为寻找最大块的1矩阵问题,然后通过奇异值分解技术来解析0/1矩阵,并按照奇异值降序排列依次求出对应的行特征向量与列特征向量,截取前k个奇异向量,依次在各个特征空间内进行行特征向量与列特征向量的聚类,直到得到满足阈值要求的1元素子块。该算法比处理实数集更加快速,效率更高。实验结果显示,该算法能够挖掘出包含所有1元素的子矩阵,且能够找出满足1元素个数要求的子矩阵（子矩阵中1的数量尽量多）。（3）提出了基于KL散度的双聚类的打分函数。在k-means迭代双聚类方法中,我们使用平均平方残差与KL散度作为评价函数,而在布尔矩阵的双聚类中,我们提出使用候选簇中的1元素的频率和KL散度来评价双聚类簇。KL散度打分函数对基因数据矩阵进行归一化操作,解决了数据标准化的问题,实验证明它的时间复杂度低于平均平方残差。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.2 课题引出
• 1.3 聚类的重要性及其应用
• 1.4 基因表达谱公共数据库
• 1.5 论文主要工作
• 1.6 论文组织结构
• 第二章 聚类分析及经典算法
• 2.1 聚类类型
• 2.2 相关概念
• 2.3 聚类算法
• 2.4 本章小结
• 第三章 双聚类算法
• 3.1 传统聚类算法存在的问题
• 3.2 双聚类算法概述
• 3.2.1 双聚类算法引入的原因
• 3.2.2 双聚类相关知识
• 3.2.3 国内外主要的双聚类算法
• 3.3 本章小结
• 第四章 K-闭集双聚类算法
• 4.1 相关概念
• 4.1.1 基本概念与问题定义
• 4.1.2 双聚类模型
• 4.2 双聚类算法的策略
• 4.2.1 双聚类算法
• 4.2.2 KL散度打分函数
• 4.3 实验及其分析
• 4.3.1 实验数据的准备
• 4.3.2 实验结果及其分析
• 4.3.3 算法性能分析
• 4.4 本章小结
• 第五章 奇异向量空间双聚类算法
• 5.1 双聚类布尔矩阵（0/1矩阵）的原因
• 5.2 奇异值向量空间双聚类算法
• 5.2.1 相关知识
• 5.2.2 问题定义
• 5.2.3 奇异值向量空间双聚类算法
• 5.2.4 KL散度评价函数
• 5.3 实验结果及分析
• 5.4 算法分析
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 研究总结
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文与参加的研究工作