基因表达数据的聚类算法设计与分析

论文摘要

DNA的微阵列技术（microarray）使得在重要的生物过程中同时检测大量的基因表达水平变得可能。揭示隐藏在基因表达数据中的基因模式可以提供一个可以加深对功能性基因的理解的重要机会。但是,巨大的基因数目和生物网络的复杂性增加了理解和解释这些基因的挑战。而解决这个挑战的第一步工作就是利用聚类技术,因为它是从底层的数据中揭示自然结构和识别有意义的模式的数据过程中的重要步骤。本文的工作就是设计并研究针对基因表达数据的有效的聚类算法。本文的主要工作为两部分内容:第一部分工作中,本文提出一个基于最小生成树的聚类算法,叫做基于最小生成树的不定划分的聚类算法（a MST-based Uncertain Partition clustering algorithm,MUP）。它能够快速有效地聚类分析基因表达数据。MUP算法的最大特点是:1,与其他基于最小生成树的算法的不同之处是不相容边的确定方法。MUP算法采用两个连续的步骤来完成:滑动窗口来识别当前簇的潜在的不相容边和利用目标函数来确定真正的将被剪断的不相容边。2,在没有先验知识的情况下,能够自动确定簇的数量。3,在具有噪声的背景中仍然能够发现有意义的基因模式。在用MUP算法分别分析两个公开的且流行的基因表达数据集,Wen的数据集和Iyer的数据集时,得到了很好的聚类结果。这说明MUP算法对大规模的基因表达数据是有效的。第二部分工作中,本文研究多视图的正交子空间聚类算法在应用基因表达数据时的聚类质量。正交子空间聚类算法已经成功地应用在其他一些领域,比如文本聚类,图像数据聚类等。理论上它可以用于分析基因表达数据,所以本文采用另一个公开的且流行的基因表达数据,Cho的数据集,来研究分析正交子空间聚类算法在基因表达数据集上的聚类效果和意义。通过实验分析,本文得出结论,正交子空间算法也能够从多个侧面很好的分析基因表达数据集。本文中的MUP算法和多视图的正交子空间聚类算法都能够有效的分析基因表达数据,它们为基因表达数据的研究和下一步的其他工作提供了有力的支持。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景及意义
• 1.2 国外研究现状
• 1.3 本文的研究工作与创新
• 1.4 本文的章节安排
• 第二章 基因表达数据分析综述
• 2.1 基因表达数据分析基础
• 2.1.1 基因表达数据矩阵
• 2.1.2 基因表达数据的预处理
• 2.1.3 分析的不同层次
• 2.2 相似性度量方法
• 2.3 聚类算法综述
• 2.3.1 基于划分的聚类算法
• 2.3.2 层次聚类算法
• 2.3.3 图论的聚类算法
• 2.4 本章小结
• 第三章 MUP聚类算法
• 3.1 MST的表示和构建
• 3.2 MUP算法中的相似性度量方法
• 3.3 MUP算法描述
• 3.3.1 算法流程
• 3.3.2 识别潜在的不相容边
• 3.3.3 确定真正的不相容边
• 3.4 MUP算法的评价
• 3.4.1 整体评价
• 3.4.2 时间复杂度
• 3.4.3 算法优点
• 3.4.4 参数讨论
• 3.5 本章小结
• 第四章 实验分析MUP算法
• 4.1 实验分析Wen的数据集
• 4.2 实验分析Iyer的数据集
• 4.3 本章小结
• 第五章 多视图的正交的聚类算法
• 5.1 直接正交聚类算法
• 5.2 正交子空间聚类算法
• 5.2.1 算法描述
• 5.2.2 实验和分析
• 5.3 本章小结
• 第六章 总结和展望
• 参考文献
• 发表论文和科研情况说明
• 致谢