下载文档原格式
基因共表达网络的构建及其相关性分析近年来，随着高通量技术的发展，基因数据的产出速度也在不断加快。
然而，单个基因的研究往往无法发现复杂疾病背后的机制，而对基因共表达网络的构建及其相关性分析能够探索基因之间的相互作用，从而揭示得疾病的本质。
基因共表达网络是指通过计算基因表达量的相似性，将基因相互联系起来形成的网络。
与传统的研究方式不同，基因共表达网络将基因看做一个整体，旨在研究基因的相互影响，从而更好地理解生物系统的复杂性。
当前，基因共表达网络已被广泛地应用于多种研究领域，比如疾病筛选、药物开发、基因调控网络的重构等。
构建基因共表达网络的基本步骤包括数据预处理、基因表达数据标准化、基因表达相关系数计算、筛选相关性达到一定标准的基因，并将它们构成一个网络图等。
常用的数据预处理方法包括质量控制、归一化、去除批次效应等。
目前主要有Pearson相关系数、Spearman相关系数和互信息等方法用于基因表达的相关系数计算。
在筛选相关性较高的基因时，常用的方法有阈值法、P值法、False Discovery Rate（FDR）法或者公认的基因相关模型等。
基因共表达网络分析不仅关注单个基因，更重视整体上基因之间的协同作用与相互关联，需要从全局的角度去探究基因网络中的基因间相互作用关系。
基因网络分析的主要内容包括度数分布、节点中心性、聚类分析和模块检测。
节点度数分布是指节点在整个网络中的连接数分布状况，通常用来表征网络的复杂性和稳健性。
而节点中心性能够评估各个节点在网络中的重要性，并说明节点在整个网络结构中所处的位置。
常见的节点中心性指标包括度中心性、介数中心性、接近中心性等。
聚类分析是基于节点的相似性来讲整个网络划分成若干个子网络并对其进行进一步分析的一种方法。
聚类分析可以使得相似的基因或样本聚集在一起，方便对其进行进一步的生物学研究。
常见的聚类算法包括Hierarchical Clustering和K-Means 算法等。
高维数据降维算法及其在聚类分析中的应用在数据领域，随着科技的发展和数据规模的爆炸式增长，高维数据的处理成为一项重要的技术挑战。
高维数据是指具有大量特征的数据集，例如在图像识别中，每个像素都可以看作一个特征，因此图像可以表示为一个高维向量。
然而，高维数据的处理复杂而困难，在实际应用中往往需要进行降维处理，以便提高计算效率和准确性。
本文将介绍高维数据降维算法及其在聚类分析中的应用。
一、高维数据降维算法的背景和意义高维数据降维算法的主要目的是将高维数据映射到低维空间中，同时保持数据的准确性和信息完整性。
在现实生活中，高维数据具有众多的特征，其中很多特征可能是冗余的或噪声的。
这些冗余特征会增加数据处理的复杂性，并且可能导致算法的过拟合问题。
另外，高维数据的存储和计算需求也非常高，对硬件资源有较大的要求。
因此，采用降维算法能够有效地减少数据的维度，提高数据处理的效率和精确度。
二、常见的高维数据降维算法1. 主成分分析（PCA）主成分分析是一种最常见和经典的降维算法，它通过线性变换将数据映射到新的坐标系中。
在新的坐标系中，数据的第一个主成分方向上的方差最大，第二个主成分方向上的方差次大，以此类推。
通过选择保留的主成分数量，可以实现数据的降维。
主成分分析在许多领域有着广泛的应用，如图像处理、人脸识别和基因表达分析等。
2. 线性判别分析（LDA）线性判别分析也是一种常用的降维算法，它与主成分分析不同的是，LDA主要关注的是类别信息。
LDA通过将数据投影到一个低维子空间中，使得不同类别的样本能够更好地分离。
与PCA相比，LDA在保留数据信息的同时，还保留了类别之间的区分度，因此在分类和识别问题中具有更好的性能。
3. t-SNEt-SNE是一种非线性降维算法，被广泛用于可视化高维数据。
它通过定义高维空间和低维空间中样本之间的相似度，将高维数据映射到低维空间。
t-SNE在处理高维数据时，能够更好地保持数据的局部结构，将相似的样本映射到相邻的低维点上，从而呈现出良好的可视化效果。
cluster基因序列摘要：一、引言二、cluster基因序列的定义和作用三、cluster基因序列在生物科学中的应用四、cluster基因序列在医学领域的应用五、cluster基因序列的未来发展及挑战正文：cluster基因序列是一种在生物体内发挥重要作用的基因序列，具有高度的生物学意义。
在本文中，我们将详细介绍cluster基因序列的定义、作用，以及在生物科学和医学领域的应用和挑战。
首先，让我们了解一下cluster基因序列的定义。
cluster基因序列是指在基因组中，具有相近序列特征的一组基因。
这些基因通常在生物体的生长发育、代谢调控等过程中发挥重要作用。
cluster基因序列可以通过生物信息学方法进行预测和分析，为研究生物系统的功能和调控机制提供重要信息。
接下来，我们来探讨一下cluster基因序列的作用。
在生物体内，cluster 基因序列可以作为生物过程的关键调控因子。
例如，在肿瘤发生发展中，一些cluster基因序列可能发生突变或失调，从而导致细胞生长失控，最终形成肿瘤。
因此，研究cluster基因序列的作用和调控机制对于揭示生物过程的奥秘具有重要意义。
在生物科学领域，cluster基因序列被广泛应用于基因功能预测、基因表达调控、蛋白质互作网络构建等方面。
通过研究cluster基因序列，科学家们可以更好地理解生物体的生长发育、适应性进化等过程。
此外，cluster基因序列还可以用于生物标记物的发现，为疾病诊断和治疗提供新思路。
在医学领域，cluster基因序列的研究成果已经开始为临床实践带来变革。
例如，基于cluster基因序列的生物标志物可以为肿瘤的早期发现、病情监测和疗效评估提供重要依据。
此外，研究cluster基因序列在疾病中的作用机制，可以为药物研发提供新的靶点。
然而，cluster基因序列在医学领域的应用仍面临许多挑战，如数据质量、分析方法等方面的问题，需要进一步研究和改进。
cluster基因序列摘要：1.概述cluster 基因序列2.cluster 基因序列的特点3.cluster 基因序列的应用4.我国在cluster 基因序列研究方面的进展正文：1.概述cluster 基因序列Cluster 基因序列，又称为簇基因序列，是指在基因组中相互关联的一系列基因。
这些基因在进化过程中保持相对稳定的位置，并协同参与生物体的某些生物学功能。
簇基因序列的研究有助于我们深入了解基因组结构、基因功能及基因调控等方面的问题。
2.cluster 基因序列的特点Cluster 基因序列具有以下几个特点：（1）紧密相邻：簇基因序列中的基因在基因组中呈连续排列，相互之间的距离相对较近。
（2）功能相关：簇基因序列中的基因通常具有相似的生物学功能，它们协同作用以完成某一生物学过程。
（3）协同进化：簇基因序列在进化过程中保持相对稳定的位置，它们之间的相互作用关系也相对稳定。
3.cluster 基因序列的应用Cluster 基因序列的研究在多个领域具有重要意义，包括：（1）基因组结构分析：簇基因序列有助于我们了解基因组中的基因分布及排列规律。
（2）基因功能研究：簇基因序列中的基因通常具有相似的功能，可以通过研究其中一个基因来推测其他基因的功能。
（3）基因调控：簇基因序列中的基因可能受到相似的调控机制，研究这些调控机制有助于深入了解基因表达调控。
（4）疾病研究：簇基因序列中的基因可能与某些疾病的发生有关，研究这些基因可以为疾病诊断和治疗提供新的思路。
4.我国在cluster 基因序列研究方面的进展我国在cluster 基因序列研究方面取得了显著成果。
近年来，我国科学家利用簇基因序列信息，深入研究了多种生物的基因组结构、基因功能及基因调控等方面问题，为相关领域的研究提供了有力支持。
同时，我国还积极参与国际合作项目，与国际同行共同探讨簇基因序列研究的最新进展。
基因表达谱数据分析方法基因表达谱是对生物体内基因表达情况的记录，通过对基因表达谱的分析，可以了解到基因在不同条件下的表达状态，从而揭示生命现象的本质和规律。
这对于研究基本生物现象、发现新的治疗手段等具有重要的意义。
随着高通量技术的发展，获取基因表达谱数据已经成为了常规操作。
但是，如何对这些数据进行分析和处理，是一个相当复杂的问题。
本文将介绍基因表达谱数据分析的基本方法和技巧。
我们将从预处理数据、差异分析、聚类分析、通路分析和生物信息学工具等几个方面进行论述。
一、预处理数据首先，我们需要将原始数据进行预处理，去除质量较差的数据，检查样本之间的差异和异常值等。
预处理过程旨在保证数据的准确性和可靠性，为后续的分析奠定基础。
二、差异分析差异分析是对基因表达谱数据进行质量评估和过滤的关键步骤。
常用的差异分析方法包括T检验、方差分析、Wilcoxon秩和检验等。
差异分析的目标是找出在不同实验条件下，哪些基因的表达发生了变化。
这是为了找到有生物学意义的差异基因集合并进一步进行研究。
三、聚类分析聚类分析是将基因表达谱数据中的基因和样本分别分成若干类，使得同一类中的基因或样本具有相似的表达模式，不同类之间具有较大的差异。
这样的分类结果有助于我们找出基因表达谱数据中的模式。
聚类分析常用的方法包括层次聚类和k-平均聚类等。
四、通路分析通路分析是将差异基因集合与特定生物过程或通路进行关联，以揭示差异基因集合在生物学上的意义。
通常，通路分析需要利用基因注释或生物信息学数据库中的信息，将差异基因集合与通路相对应，从而找到可能受到影响的通路。
五、生物信息学工具最后，利用生物信息学工具进行综合分析和可视化。
有很多生物信息学工具可以用来对基因表达谱数据进行分析和可视化，比如R、Python、Cytoscape等。
这些工具可以帮助我们更好地理解和解释基因表达谱数据中的生物学意义。
总结：基因表达谱数据分析是序列分析的一个重要分支，广泛应用于生物信息学、系统生物学和合成生物学等领域。
基因组学研究中的表达谱数据分析方法解析概述：基因组学研究是研究生物体基因组的编码和非编码序列的科学。
在基因组学研究中，表达谱数据是一种重要的数据类型，由于其高维度和复杂性，需要采用一系列的分析方法和技术来解析。
本文将介绍基因组表达谱数据的分析方法，包括数据预处理、差异表达分析、聚类分析、富集分析以及网络分析。
一、数据预处理：数据预处理是基因组表达谱数据分析的第一步，目的是清除原始数据中的噪声、去除非生物学的变异以及纠正技术上的偏见。
常用的数据预处理步骤包括数据质量控制、归一化和基因过滤。
1. 数据质量控制：首先需要对原始数据进行质量控制，该步骤可通过查看测序质量分数和测序错误率来评估。
常用的工具有FastQC和Trimmomatic等。
该步骤的目的是排除测序引入的噪声。
2. 归一化：由于不同样本之间的表达量存在显著的差异，我们需要对数据进行归一化处理，以消除样本间的偏差。
常用的归一化方法有TPM、FPKM和RPKM等。
归一化后的数据便于后续的比较和统计分析。
3. 基因过滤：在分析表达谱数据时，一些基因的表达量非常低，对分析结果产生较小的影响并增加运算复杂性。
因此，我们通常会对表达量低于一定阈值的基因进行过滤处理，从而提高分析效率。
常用的过滤标准包括表达量百分位数和表达量阈值。
二、差异表达分析：差异表达分析是基因表达谱数据分析的核心内容之一，旨在发现不同条件下存在差异表达的基因。
通常，差异表达分析包括基于假设检验的方法和机器学习方法。
1. 基于假设检验的方法：这类方法通常基于统计学原理，将样本分组，通过计算差异表达的显著性水平来判断基因是否差异表达。
常用的方法包括Student's t-test、Wilcoxon秩和检验和Fisher's确切检验等。
这些方法基于不同的假设，在数据有明确的分布前提下，可以得到比较可靠的差异表达结果。
2. 机器学习方法：机器学习方法对差异表达分析具有较高的灵活性和预测能力。
单细胞测序聚类树近年来，随着单细胞测序技术的快速发展，人们对于单细胞的研究逐渐深入。
单细胞测序能够揭示单个细胞的基因表达情况，为我们提供了研究生物系统的全新视角。
在单细胞测序的基础上，聚类树分析成为了解细胞类型和细胞状态的重要工具之一。
本文将介绍单细胞测序聚类树的概念、构建方法和应用。
聚类树是一种将细胞根据其基因表达情况进行分类和分组的方法。
在单细胞测序中，每个细胞都会被测量其上千个基因的表达水平。
通过对这些基因表达数据进行聚类分析，我们可以将相似的细胞聚集在一起，形成一个聚类树。
聚类树能够帮助我们理解细胞类型的分布和细胞状态的变化，从而揭示生物系统的复杂性。
构建单细胞测序聚类树的关键步骤包括数据预处理、细胞聚类和树的构建。
在数据预处理阶段，需要对原始的单细胞测序数据进行质量控制、噪声过滤和归一化处理。
接下来，通过聚类算法将细胞分为不同的群集。
最常用的聚类算法包括k-means、层次聚类和DBSCAN等。
在细胞聚类完成后，可以利用聚类结果构建聚类树。
常用的树构建方法包括自顶向下和自底向上两种。
自顶向下的方法从所有细胞开始，逐渐将细胞分为不同的群集，直到每个细胞成为一个单独的叶节点。
自底向上的方法则从每个细胞开始，逐渐将细胞合并为更大的群集，直到所有细胞都被合并为一个根节点。
单细胞测序聚类树在许多研究领域中得到了广泛的应用。
首先，聚类树可以帮助我们鉴定和分类细胞类型。
通过比较聚类树中不同叶节点的基因表达模式，我们可以确定不同细胞类型的特定基因标记，从而鉴定其身份。
其次，聚类树可以揭示细胞状态的变化。
在聚类树中，不同的分支和节点代表了不同的细胞状态。
通过比较聚类树的结构和细胞状态的外部信息，我们可以发现细胞状态的动态变化规律。
此外，聚类树还可以用于研究细胞间的相互作用和通讯。
通过分析聚类树中不同细胞群集的连接关系，我们可以了解细胞之间的相互作用模式和信号传递机制。
尽管单细胞测序聚类树在细胞生物学研究中具有广泛的应用前景，但也存在一些挑战和限制。
第四节 基因表达数据的聚类分析基因表达数据主要来自于两个方面，一是基因芯片，这是最主要的表达数据来源，利用基因芯片技术可以大规模并行获取基因转录结果mRNA 的数据（Schena Eet al ，1995）。
表达系列分析SAGE 和差异显示（Kozian and Kirschbaum ，1999）、蛋白质芯片等是快速检测蛋白质及其含量的另一类技术。
聚类分析是模式识别中一种非常有吸引力的方法，特别适用于模式分类数不知道的情况。
从机器学习的角度来看，有两种基本的聚类分析（Kaufman 1990），即所谓有教师聚类和无教师聚类。
在有师聚类中，对于每一类有一个参考模式，对于一个未分类的向量，通过计算选择一个最接近的参考模式，并将该向量归入该参考模式所对应的类，这实际上是一个分类问题。
而真正的聚类分析是一种无师学习（或无监督学习），没有关于聚类的先验知识，需要聚类算法根据样本之间的距离或者相似程度进行自动分类（傅京孙，1990；李介谷等，1986）。
基因表达数据聚类分析一般包括以下几个步骤：（１）确定基因表达的数据；（２）计算相似性矩阵，各个矩阵元素代表两个基因的表达是否相似；（３）选择算法进行聚类分析；（４）显示分析结果。
以下着重讨论对表达型基因芯片实验数据的处理和分析。
在一种基因芯片上往往含有成百上千个基因探针，一次可以同时检测大量基因的表达。
利用同一种芯片在不同条件下（不同时间，不同细胞，不同外界作用）进行基因表达实验，搜集表达数据，将原始数据放在一起，形成一个数据表格。
表格的每一行代表一个基因，是一个基因在不同实验条件下表达的“快照”，而每一列则代表各个基因在同一种实验条件下的表达水平。
从数学形式上来看，表格的一行数据就是一个向量，常称其为一个基因的表达模式，而表格本身就相当于一个矩阵。
聚类分析就是将这些向量按照相似程度进行归类。
对数据进行聚类分析之前，必须将包含在基因表达矩阵中的数据进行相似程度分析，并且对分析结果进行量化。
生物大数据技术如何处理基因表达数据随着科学技术的发展和生物学研究的深入，生物大数据已成为现代生命科学的关键组成部分。
其中，基因表达数据是生物大数据的重要组成部分之一。
它包含了对生物体内基因在特定时间点、组织和环境条件下的表达水平的信息。
如何高效地处理基因表达数据成为了生物大数据技术中的一个重要问题。
处理基因表达数据的第一步是数据的获取和预处理。
基因表达数据通常通过高通量测序技术（如RNA-seq和microarray）获得。
在这个阶段，数据中会包含大量的噪声和不确定性，需要进行预处理来提高数据的质量和可靠性。
预处理的过程包括数据清洗、去除噪声、去除低质量的数据点、数据标准化等。
这些预处理方法可以帮助消除测序仪器和实验操作的误差，并使不同样本之间的数据具有可比性。
经过预处理之后，基因表达数据需要进行特征提取和分析。
特征提取是将原始数据转化为更简洁、更有意义的形式的过程。
常用的特征提取方法包括基因差异分析和聚类分析。
基因差异分析可以通过比较不同条件下基因的表达水平来寻找差异表达的基因。
聚类分析可以将基因或样本分成不同的群集，寻找具有相似表达模式的基因或样本。
这些特征提取方法可以帮助研究人员快速发现基因的功能和生物过程的动态变化。
在特征提取之后，进一步的数据分析可以使用机器学习和深度学习等方法。
机器学习是一种通过训练模型来预测和分类的方法，可以根据已知的基因表达数据来建立模型，并用于预测新的未知数据。
深度学习是一种建立多层神经网络来处理复杂数据的方法，可以学习到更高级别的特征表示，并提高预测的准确性。
这些方法可以帮助研究人员更全面地理解基因表达数据，并挖掘出隐藏在数据中的模式和规律。
此外，生物大数据技术还可以结合其他生物学信息进行综合分析。
例如，可以将基因表达数据与基因组注释数据、代谢通路数据等进行整合，以获得更全面和准确的生物学信息。
这种综合分析可以揭示基因表达与基因功能、代谢通路等之间的关系，帮助研究人员更加深入地研究生物学问题。
文章编号:042727104(2008)022*******收稿日期:2007209224基金项目:国家自然科学基金资助项目(60573093);国家863计划基金资助项目(2006AA02Z329)作者简介:熊 斌贝(1980—),女,讲师;通讯作者:朱扬勇(1963—),男,教授,博士生导师.G en 2Cluster :一个基因表达数据的高维聚类算法熊 斌贝,邱伯仁,张 坤,朱扬勇(复旦大学计算机与信息技术系,上海200433)摘 要:基因表达数据聚类是分析基因之间共调控关系的重要手段.挖掘子空间中表达值存在差异但变化趋势保守的序列已成为基因表达数据聚类的主要研究内容之一.在N 2同维趋势相似定义的基础上,提出了一个基因表达数据的高维聚类算法G en 2Cluster ,将基因表达值转化为序列形式,采用无重复投影且无候选生成的序列模式挖掘策略自底向上挖掘N 2同维趋势模式,并解决了OP 2Cluster 算法不能挖掘含有项集的序列模式问题,最终得到表达值变化趋势保守的基因序列形成的N 2同维趋势簇.实验采用Breast Tumor 和MicroRNA 表达数据集,验证挖掘结果是有效的,且较OP 2Cluster 算法表现更高效率,并涵盖其结果.关键词:高维数据挖掘;聚类;基因表达数据;N 2同维趋势相似中图分类号:TP 391 文献标识码:A 揭示基因表达调控的复杂机制是后基因组时代所面临的重大挑战之一.基因表达实际上是细胞、组织、器官受遗传和环境影响的结果,可以反映特定组织或细胞内的基因在不同生理或实验条件下、在连续的时间段内不同时间点上的表达水平[1].由于同一共调控基因簇中的基因更有可能相互表达并包含在同一个细胞生命过程中,因而,在聚类后得到的基因簇中的共表达的基因上游序列挖掘保守模式,能够提高转录调控元件预测的准确程度[2],并能得到关于调控元件与相应的生理条件或环境信息间的关联.因此,基因表达数据聚类是转录调控元件及其相互作用网络研究的重要内容.基因表达数据通常是在多个条件(如组织、细胞周期的不同阶段、药物作用时间等)下度量的,它具有高维性.基于全空间的距离函数聚类方法不适合这样的高维数据,因为一个感兴趣的生物过程通常只包含基因中的小部分,且过程也可能只发生在少数条件下,即高维空间中的对象在某个子空间中相似.其中,部分条件下具有保守变化趋势但表达水平值强度存在差异的基因(如在一个维集上表现出一致的模式,但在维上的值并不一定接近),对于揭示基因序列转录调控机制有重要的生物意义[328].研究者提出的基于子空间的基因表达双向聚类方法,如BiClustering [4],pCluster [5],Maple (Maximal Pattern 2based Cluster 2ing )[6],OPSM (Order 2Preserving Submatrix )[7]等,对表达值的比例和条件顺序上都有严格约束,难以聚类某些条件下具有类似表达模式但表达水平值存在差异的基因.为解决这个问题,Liu 等提出了OP 2Clus 2ter (Oder Preserving Cluster )算法[8],但由于OPC 树的剪枝条件取决于用户定义的维数阈值,当阈值相对于全空间维数较小时,剪枝条件难以满足,OPC 树构造的代价增大,导致效率降低,并且OP 2Cluster 算法不能处理含有“顺序等价组”的模式(即含项集的序列模式).本文提出N 2同维趋势相似和N 2同维趋势模式定义,将这类基因表达数据聚类问题转换为N 2同维趋势模式挖掘问题,在高维基因表达数据的不同维组合的子空间中进行N 2同维趋势聚类,并基于此设计一个有效的基因表达数据高维聚类算法G en 2Cluster.首先将基因表达值转化为序列形式,再使用无重复投影无候选生成的序列模式挖掘策略,自底向上挖掘N 2同维趋势模式,最终得到N 2同维趋势簇,即变化趋第47卷 第2期2008年4月复旦学报(自然科学版)Journal of Fudan University (Natural Science )Vol.47No.2Apr.2008势保守的相似序列,并在算法设计上考虑了含项集的模式处理方法.实验采用两个真实数据集(Breast Tu 2mor 和MicroRNA 表达数据集),证实了G en 2Cluster 算法较OP 2Cluster 算法表现更高效率,并验证了挖掘结果的有效性.1 相关工作基因表达数据是一类高维数据,其聚类是一个高维空间聚类问题.Aggarwal 等对L k -范数进行了深入研究[9],表明L k -范数在很多情况下不适合用作高维空间的距离函数,因为在高维空间中用L k -范数作距离函数时,一个点到它的最近邻和最远邻的距离几乎是相等的.因此,基于全空间距离函数的聚类方法常常不适合高维空间.由于一个数据集中各个数据簇往往与不同的子空间有关,使得子空间数据的聚类可能比原始空间更好,所以,限制在只对原始空间的子空间而不是使用一个新的维度(例如由原始的维度线性组合成新的维度)上搜索的方法具有重要意义[10].针对基因表达数据的特性,基因表达数据聚类包括根据多个条件下的表达值对基因序列聚类,或是基于多个基因的表达情况对条件聚类,因此,需要在子空间中考察基因表达数据,具有代表的子算法是Cheng 等引入的双向聚类(BiCluster )算法[4].对于变化趋势保守的基因簇挖掘,传统的基因表达聚类方法使用相关系数定义趋势相似度,从本质上说相关系数是测量两个表达矢量所指方向的相似性,对幅度的变化不敏感,但若两个不很相似的基因表达谱在某一个突出的峰或谷特别相关时,相关系数可能给出假阳性.因此,Yang 等[5]提出了基于模式的子空间聚类算法pCluster ,在此基础上Pei 等对其进行了改进,提出了Maple 算法[6]等,但这些方法挖掘的结果要求不仅具有保守趋势,而且表达值也必须是严格成比例的.之后,Ben 2Dor 等提出OPSM 模型[7],不考虑列值的大小,发现变化趋势保守的基因簇,但其主要不足是条件严格有序[6].为寻找具有类似表达模式但表达水平值强度存在差异的关联基因,Liu 等提出一个更为一般的模型OPC [8]用以挖掘具有一致趋势的基因簇,并通过将基因表达数据转换为序列数据,将聚类问题转变为序列模式挖掘问题,虽然它将OPSM 模型包括为其一个特例,并且允许相似表达条件组成“顺序等价组”,但OP 2Cluster 算法在构造OPC 树时仍将“顺序等价组”项看作是不同顺序的序列构建OPC 树,因而不能处理这样含有项集的序列模式情况.与文献[8]不同,本文重新定义了N 2同维趋势相似用以度量基因表达谱变化趋势的保守性,并在此基础上提出了G en 2Cluster 算法,将基因表达数据聚类问题转换为N 2同维趋势模式挖掘问题,对高维基因表达数据进行N 2同维趋势聚类,挖掘得到表达水平值不同但变化趋势保守的基因簇,并考虑了“顺序等价组”产生的多项模式挖掘问题,涵盖了OP 2Cluster 聚类算法的结果.2 问题定义例1 表1表示基因芯片实验得到5个基因在4种不同条件作用下的基因表达数据集A^,一般地,用m 表示基因数目,用n 表示条件数目,表1中m =5,n =4.表1的每一行反映了一个基因在不同条件下的表达情况;每一列反映了某个条件下的所有基因的表达水平,表1中每一个元素表示第i 个基因G i 在表1 基因表达数据集Tab.1 G ene express data set G ene Condition D 1D 2D 3D 4G 19421000845670G 2992340865620G 3962820855640G 498278825660G 5972130875650第j 个组织D j 下的表达水平值.所有的m 个基因序列G i 组成的集合,称为基因序列集,用G ⌒表示;所有的n 个条件D j 组成的集合,称为条件集,用D ⌒表示.用O 表示基因和对应条件组成的对象,记为O (D 1,D 2,…,D j ,…,D n ).对所有条件而言,用L k 距离计算基因在各条件下的相似度,由于在条件D 2上,这5个基因的值相差较大,因此,全空间的L k 距离度量难以获得这5个基因的相似关系(如图1).然而从中选出3个条件(D 1,D 3,D 4),可以发现它们存在如下关系(图2),即5个基因在此3个条件作用下具有相似特点,它们的表达水平值相近.631 复旦学报(自然科学版)第47卷 从图2可以看出在n 个条件下的基因在其中某N 个条件上的表达水平值具有一定的相似性时,可以认为这些基因在这N 个条件上是相似的.当N 达到一定阈值时,那么可以认为这几个基因也是相似的(N 值可由相关领域专家指定).进一步的,基因表达数据存在固有的波动性,当基因序列在不同条件下,其表达水平值具有一定的差异,但变化趋势具有保守性时(如表2和图3所示),如G 2,G 3,G 4在条件D 1,D 2,D 3上的水平值相差较大,但它们在这3个条件上都有一致的波动趋势,因此局限于表达值间的判断方法会使得一些簇丢失真正有意义的基因对象,而它们在生物学研究中却有非常广的应用范围.表2 示例数据集Tab.2 Sample data setG ene Condition D 1D 2D 3D 4G 139428453770754G 21392865620814G 36392376515134887G 43918253211563180G 5367914211368220图3 基因之间的相似趋势关系Fig.3 Similar tendency among genes 定义1 n 维对象空间(n Dimensional Object Space ) 一个对象如果有n 个维值,形如O (x 1,x 2,…,x n ),则称O 为一个n 维对象.所有形如O (x 1,x 2,…,x n )的对象构成一个n 维对象空间F ,F =D 1×D 2×…×D n ,其中,每个D i (i =1,2,…,n )表示一个维的取值域.定义2 n 维基因对象集(n Dimensional G ene Object Set ) 将一个基因看作是一个n 维对象空间F中的对象,那么上述基因表达数据集A^就是一个n 维对象空间F 的实例,称其为n 维基因对象集,记为Σ.其中,Σ中的每个对象O 对应基因表达数据集A^(如表1)中的一个对象O ,Σ中的每个维D 表示基因表达数据集中的一个条件D (D ∈D ⌒).定义3 相近维组项(Similar Dimension Group Item ) 设O 是n 维对象空间中的一个对象,(x 1,x 2,…,x n )是以非递减顺序排列的属性值,δ是用户指定的阈值.称O 在属性D i ,D i +1,…,D i +j (n ≥i >0,n ≥j >0)上是相近的,如果,(x i +j -x i )<δ,则称属性集〈D i ,D i +1,…,D i +j 〉是相近维组项.相近维组项是因为在两个或多个条件下值的影响不是很明显时,即几个具有相同表达水平的条件可能是属于关于在疾病或基因变异过程中一个阶段或时间点的同一个组[8].定义4 对象维序(Object Dimensional Order ) 给定对象O (x 1,x 2,…,x n ),如果x l ≤x k ,则称O 有维序D l ;D k ,读做D l 先于D k .如果x l ,x k 相近,则称D l 和D k 序无关.定义5 对象维序列(Object Dimensional Sequence ) 将一个对象O 的值x 1,x 2,…,x n 按升序排列为x k 1≤x k 2≤…≤x kn ,那么对应的维D k 1,D k 2,…,D ki ,…,D kn 称为一个对象维序列,记为O 〈D k 1,D k 2,…,D ki ,…,D kn 〉.其中,若D ki 1,D ki 2,…,D kij 是序无关的,则用(D ki 1,D ki 2,…,D kij )表示,这时对象维序列731 第2期熊 斌贝等:G en 2Cluster :一个基因表达数据的高维聚类算法 表示为O 〈D k 1,D k 2,…,(D ki 1,D ki 2,…,D kij ),…,D kn 〉.一个对象维序列对应n 维基因对象集Σ中的一个对象.注1 对象维序列中对象的值允许在后续G en 2Cluster 算法实现时采用降序排列,聚类效果相同.这样,n 维基因对象集Σ可转换为m 个对象维序列组成的n 维序列数据库(DSDB ,Dimensional Se 2quence Database ),记为Δ{O 1,O 2,…,O i ,…,O m }.例2 如表2是原始基因表达数据集(设相近维组项阈值δ=240),将其转换为维序列数据库Δ形式,如表3所示.表3 表2转换后的维序列数据库ΔTab.3 DSDB Δfrom Tab.2SeqId Sequence O 1〈D 4D 2(D 1D 3)〉O 2〈D 3(D 2D 4)D 1〉O 3〈D 3D 2D 4D 1)〉O 4〈D 3D 4D 2D 1〉O 5〈D 4D 3D 2D 1〉 转换方法:首先将原始基因表达数据集对应到4维基因对象集Σ,这样原始基因表达数据集中的每个基因对象用对象O表示,然后对每一个对象O 按基因表达水平值升序排列,得到对象维序列,所有对象转换后得到的维序列集合组成维序列数据库Δ.例如对对象O 1按基因表达水平值升序排列后得到对象维序列O 1〈D 4D 2(D 1D 3)〉,其中(D 1D 3)为相近维组项,因为(3942-3740)<240.转换后的维序列数据库Δ如表3所示.定义6 子序列(Subsequence ) 给定对象维序列O 1=〈D 1,D 2,…,D n 〉及O 2=〈D /1,D /2,…,D /m 〉(m ≤n ),如果存在1≤i 1<i 2<…<i m ≤n ,使得D /1,ΑD i 1,D /2ΑD i 2,…,D /m ΑD im ,则称O 2是对象维序列O 1的子序列,或称O 1包含O 2.定义7 同趋势(Similar Tendency ) 给定维序列数据库Δ中任意两个对象维序列O i (D i 1,D i 2,…,D in )和O j (D j 1,D j 2,…,D ji ),以及l 个维D k 1,D k 2,…,D kl ,若对于O i 和O j ,都有D k 1;D k 2;…;D ki ,则称O i 和O j 在l 个维D k 1,D k 2,…,D ki 上是同趋势的.其中,{D 1,D 2,…,D n }={D i 1,D i 2,…,D in }={D j 1,D j 2,…,D ji },{D 1,D 2,…,D n }={D k 1,D k 2,…,D ki }.定义8 N 2同维趋势模式相似(N 2Same Dimensional T endency Similar )和N 2同维趋势模式(N 2Same Di 2mensional T endency Pattern ) 给定一个n 维序列数据库Δ,如果Δ中的k 个对象维序列O 1,O 2,…,O i ,…,O k 在N (N ≤n )个相同维(D k 1,D k 2,…,D kN )上是同趋势的,那么称这k 个对象维序列是N 2同维趋势相似的.其中,N 个相同维组成的子序列〈D k 1,D k 2,…,D kN 〉称为N 2同维趋势模式,记为pattern .定义9 维支持度(Dimensional Support ) N 2同维趋势模式pattern 的维支持度是模式pattern 的长度,记为di m 2sup .定义10 簇支持度(Cluster Support ) N 2同维趋势模式pattern 的簇支持度是维序列数据库Δ中包含pattern 的对象维序列的个数,记为cl u 2sup .注2 一般地,相对支持度为cl u 2sup/|Δ|(|Δ|表示维序列数据库中对象维序列的个数),简单起见,这里以绝对数表示.定义11 N 2同维趋势簇(N 2Same Dimensional Tendency Cluster ) k 个N 2同维趋势相似的对象维序列组成的集合(O 1,O 2,…,O i ,…,O k ),若k 满足簇支持度阈值则称(O 1,O 2,…,O i ,…,O k )为N 2同维趋势簇.例3 如表2,取N =3,在维D 3,D 4,D 1上,对象O 2,O 3,O 4有相同的趋势,因此,对象O 2,O 3,O 4组成一个32同维趋势簇,维D 3,D 4,D 1组成的子序列〈D 3D 4D 1〉称为32同维趋势模式.推论1 设n 维对象O 1,O 2,…,O m ∈F ,如果它们在N 个维D 1,D 2,…,D n 上是N 2同维趋势相似的,则它们也一定在该N 个维的子集N -1个维上是N -12同维趋势相似的.定义12 N 2同维趋势聚类(N 2Same Dimensional Tendency Clustering ) 给定一个维序列数据库Δ及簇支持度cl u 2sup ,将维序列数据库中的对象维序列O 1,O 2,…,O m 聚成N 2同维趋势簇,并且每个簇中的对象维序列个数大于等于cl u 2sup ,则称该过程为N 2同维趋势聚类.N 2同维趋势聚类是有重叠聚类.例4 如表3.(O 2,O 3,O 4)是一个在维D 3,D 4,D 1上的32同维趋势簇,(O 3,O 4,O 5)是一个在维D 3,831 复旦学报(自然科学版)第47卷 D 2,D 1上的32同维簇,对象O 3和对象O 4在两个32同维趋势簇中均有出现,因此,它们是有重叠的聚类.经过上述转换,基因表达数据聚类问题则可看作是在经过排序后的维序列数据库中挖掘N 2同维趋势模式的问题.3 G en 2Cluster 算法基因表达数据N 2同维趋势聚类算法G en 2Cluster (G ene Express Data N 2Same Dimensional Tendency Clustering )的目的是对n 维对象空间F 上的m 个基因G 1,G 2,…,G m ,根据它们在n 个不同条件下的基因表达水平值,进行N 2同维趋势聚类,得到所有的N 2同维趋势簇,这些簇之间是允许有重叠的,且簇中的对象在对应的N 个维上具有相似的变化趋势.G en 2Cluster 算法包括两个阶段:第一阶段(预处理阶段)是按照例2中所给的转换方法将原始基因表达数据集转换为对象维序列形式,构成维序列数据库Δ;第二阶段(序列模式挖掘阶段)是在维序列数据库Δ中挖掘N 2同维趋势模式,每个结果模式表示一个由N 个维所形成的维子空间,包含该模式的基因对象,即它们在这N 个维上的表达值变化趋势保守,这些基因对象形成一个N 2同维趋势簇.为算法描述方便,先给出几个相关定义.定义13 含有项的前缀(Prefix with ItemSet ) 给定对象维序列的子序列O 1=〈D 1,D 2,…,D n 〉,O 2=〈D 1’,D 2’,…,D m ’〉(m ≤n ).O 2为O 1的前缀,当且仅当1)D i ’=D i (i ≤m -1);2)D m ’ΑD m ;3)在(D m -D m ’)中的所有项按字母序排列在D m ’之后.定义14 含有项的投影(Projection with ItemSet ) 给定两个对象维序列的子序列O 1,O 2,其中O 2是O 1的子序列,即O 2ΑO 1,O 1的子序列O 3(O 3ΑO 1)被称为O 1关于前缀O 2的投影,当且仅当:1)O 2是O 1的前缀;2)不存在O 3的超集O 4,即(O 3ΑO 4,O 3≠O 4),使得O 4是O 1的子序列并且O 2是O 4的前缀.由定义13和14有O 3=〈D 1,D 2,…,D n 〉是O 1关于前缀O 2=〈D 1,D 2,…,D m -1,D m ’〉的投影(m ≤n ).O ’=〈D //m ,D m +1,…,D n 〉是O 1关于前缀O 2的后缀,其中D //m =(D m -D m ’).例如,〈D 4〉,〈D 4D 2〉是序列〈D 4D 2(D 1D 3)〉的前缀,但是〈D 2(D 1D 3)〉不是前缀.〈(D 1D 3)〉是序列〈D 4D 2(D 1D 3)〉关于前缀〈D 4D 2〉的后缀.定义15 含有项的投影数据库(Projected Database with ItemSet ) 维序列数据库中所有关于子序列O 的投影组成的集合称为O 的投影数据库,记为DS S D |O .例5 如表4所示的维序列数据库,子序列〈D 1D 2〉相对于对象维子序列〈D 5D 1D 2D 3D 4〉的投影为〈D 3D 4〉,子序列〈D 1D 2〉的投影数据库如表5所示.表4 示例维序列数据库Tab.4 An example of dimensional sequence databaseSeqId Sequence O 1〈D 5D 1D 2D 3D 4〉O 2〈D 5D 1D 2D 3D 4〉O 3〈D 1D 5D 2D 3D 4〉表5 子序列〈D 1D 2〉的投影数据库Tab.5 The project database of 〈D 1D 2〉SeqId Sequence O 1〈D 3D 4〉O 2〈D 3D 4〉O 3〈D 3D 4〉 定义16 前缀树(Prefix Tree ) 维序列数据库的前缀树是指满足以下条件的树:i )除根结点外,每条路径都对应一个序列;ii )按照字母序排列,左兄弟结点小于右兄弟结点;iii )子结点都由父结点对应序列的投影数据库中支持度大于阈值的项组成.表4前缀树如图4(见第140页)所示.采用前缀投影方法挖掘序列模式的过程中,将会出现大量重复的投影数据库,造成相同数据库的重复扫描.为避免这样的重复扫描,文献[11]提出了一种无重复投影的序列模式挖掘策略:每个序列的投影数931 第2期熊 斌贝等:G en 2Cluster :一个基因表达数据的高维聚类算法 据库用一系列指向原始数据库的指针表示.例如,〈D 1D 2〉的投影数据库用指向原始数据库(表4)中第一个序列的第4个元素,第2个序列的第4个元素,第3个序列的第4个元素的三个指针表示.那么,当且仅当这一系列指针相等时则认为这两个投影数据库相等.然而,这个判断不能直接应用于含有项集的序列模式挖掘中.图4 表4的前缀树Fig.4 The prefix tree for Tab.4表6 带有项集的维序列数据库Tab.6 Dimensional sequence database with itemset SeqId Sequence O 1〈(D 1D 2)(D 2D 3D 4)〉O 2〈(D 1D 2)(D 2D 3D 4)〉O 3〈(D 1D 2)(D 2D 4)〉 例6 维序列数据库如表6所示,维支持度为2.若已发现前缀序列〈(D 1D 2)〉,则计算前缀〈D 2〉的投影数据库时,发现〈D 2〉的投影数据库和〈(D 1D 2)〉的投影数据库相等.按照文献[11]给出的推论和定理,只需要将〈(D 1D 2)〉的子结点同时作为〈D 2〉的子结点,但这种情况下,〈(D 2D 3)〉,〈(D 2D 3D 4)〉这样的序列模式将丢失.因此,文献[11]的方法不适合挖掘具有相近维组项的N 2同维趋势模式.为解决这个问题,下面引入集合内扩展和集合间扩展定义.定义17 集合内扩展(I 2EXTEND ) 指相邻维组项集合内的扩展,例如前缀树中的结点〈D 1〉扩展为〈(D 1D 2)〉.定义18 集合间扩展(S 2EXTEND ) 指属性集合间的扩展,例如前缀树中的结点〈D 1〉扩展为〈D 1D 2〉.定义19 局部伪投影(Local Pseudo Projec 2tion ) 每个序列的投影数据库用一系列指向原始数据库的指针表示,这一系列指针的数组称为局部伪投影.定义20 伪投影(Pseudo Projection ) 对于含有项集的情况,每个序列的投影数据库考虑项集部分,指向原始数据库的指针是一个集合,称指针集合的数组为伪投影.例7 例6中序列〈D 2〉和〈(D 1D 2)〉的伪投影和局部伪投影如图5所示,尽管〈D 2〉和〈(D 1D 2)〉的局部伪投影相同,但是它们的伪投影并不相同.图5 含有项集序列的伪投影Fig.5 Pseudo 2projection of sequence with itemset定理1 两个投影数据库相等,当且仅当伪投影相等[11].证 投影数据库是原始数据库的一个子集,伪投影是指向原始序列数据库的指针集合.如果两个序列的投影数据库所对应的指针集合完全相同,则两个序列有完全相同的投影数据库.证毕.推论1 如果单向杂凑函数的冲突率可以忽略,那么两个投影数据库相等,当且仅当两个投影数据库041 复旦学报(自然科学版)第47卷 伪投影的哈希值相等.根据推论1,在每生成一个投影数据库的过程中,计算投影数据库的哈希值,将其保存在前缀树中,在前缀树生成过程中,如果某个结点p 对应的哈希值等于当前结点w 的哈希值,则表示这两个投影数据库相同.因此,不需要继续扫描重复的投影数据库,只需要将p 在投影数据库中的子结点同时作为w 的子结点即可[11].定理2 当前缀树中两个结点对应的伪投影相同时,处理这两个结点可以合并.当两个序列的局部伪投影相同时,通过S 2EXTEND 生成的结点相同.证 如果两个序列O 1和O 2的局部伪投影相同,那么进行S 2EXTEND 时的任意频繁项假设为i ,可知i 必然与O 1和O 2的最后一个项不属于同一个元素.因此,如果这个项是频繁的当且仅当这个项在投影数据库中是频繁的.如果两个序列的伪投影相同,局部伪投影也必然相同,S 2EXTEND 必然相同.由于伪投影定义的是每个项进行扩展时的指针集合,必然从这些指针集合中发现I 2EXTEND 结点I 2EXTEND 和S 2EXTEND 结点都相同,因此可进行归并处理.证毕.根据定理2,尽管〈D 2〉和〈(D 1D 2)〉伪投影的哈希值不等,但是两者仍然可以共享S 2EXTEND 的结点,而在〈D 2〉进行I 2EXTEND 时,又发现〈(D 2D 3)〉和〈(D 2D 4)〉与〈(D 1D 2)D 3〉和〈(D 1D 2)D 4〉的伪投影相同,进而可以将D 3和D 4两个结点合并,图6给出了表6的压缩前缀树.利用投影数据库相等的一些必要条件可以提高搜索的效率,即如果两个前缀序列拥有相同的投影数据库,则这两个投影数据库的大小必然相同,前缀序列的最后一项也必然相同[11].图6 表6对应的压缩前缀树Fig.6 Compressed prefix 2tree for Tab.6综上分析可得N 2同维趋势聚类算法G en 2Cluster.算法1 G en 2Cluster (s ,D ,cl u 2sup ,F )输入: 预处理阶段转换后的维序列数据库D ,簇支持度阈值cl u 2sup .输出: N 2同维趋势模式集F ,即满足簇支持度阈值条件的所有长度的同维趋势模式以及所对应的序列号.1)s =NULL ;2)扫描一遍维序列数据库D 得到长度为1的频繁项集w ;3)for each w do4) 建立s 指向w 的指针并设置s .att r 为S 2EXTEND ; //每个结点属性s.att r 表示边的扩展是I 2EXTEND 还是S 2EXTEND //第一个结点属性必须是S 2EXTEND ,并需要首先做单独处理141 第2期熊 斌贝等:G en 2Cluster :一个基因表达数据的高维聚类算法 5) 创建w 的伪投影P w ;6) call iSet 2G ePM (w ,D ,cl u 2sup ,P w );7) 遍历前缀树s 并结合s .att r 到N 2同维序列模式集F .算法2 iSet 2G ePM (s ,D ,cl u 2sup ,P s ) //含有项集的N 2同维趋势模式挖掘算法输入:树结点s ,整个维序列数据库D ,最小支持度阈值cl u 2sup 和s 的伪投影P s .输出:前缀树.1)扫描一遍P s ,计算s 的局部伪投影的哈希值d ’并进而计算伪投影的哈希值d ;2)按照必要条件搜索已经生成的前缀树;3)if exist w.d =s.d do4) 找到s 的父结点p ;5) 将w 作为p 的子结点,不改变p.r ;6) 删除s ;7)return8)if exist w.d ’=s.d ’do9) for each w.att r =S 2EXTEND 的结点r do10) 将r 作为s 的子结点,并置相应的s.att r =S 2EXTEND ;11) 根据P s 扫描一遍D 找到I 2EXTEND 的结点r ;12) for each r do13) 将r 作为s 的子结点,并置相应的s.att r =I 2EXTEND ;14) 生成r 的投影数据库P r ;15) call iSet 2G ePM (r ,D ,cl u -sup ,P r );16) return17) 结合P s 扫描一遍D 得到所有的I 2EXTEND 结点r 和S 2EXTEND 结点t ;18) if P s 的长度小于cl u 2sup 或者不存在r 和t19)return20)for each r do21) 将r 作为s 的子结点,并置相应的s.att r =I 2EXTEND ;22) 生成r 的投影数据库P r ;23) call iSet 2G ePM (r ,D ,cl u 2sup ,P r );24)for each t do25) 将t 作为s 的子结点,并置相应的s.att r =S 2EXTEND ;26) 生成t 的投影数据库P t ;27) call iSet 2G ePM (t ,D ,cl u 2sup ,P t );28)return算法挖掘结果得到的序列模式集F ,再根据用户定义的维支持度阈值N ,对结果序列模式集F 进行截断,取得满足阈值条件的N 2同维趋势簇.G en 2Cluster 算法在计算判断模式是否频繁计算支持度同时,保留该模式所在的序列号.包含各个N 2同维模式的基因即为在相同N 个条件下具有保守变化趋势的序列.G en 2Cluster 算法能挖掘任意维数组合的子空间中的簇,并考虑了含有项集的序列模式挖掘问题,解决了文献[8]不能处理含有项集的序列模式问题.注3 OP 2Cluster 算法在构造OPC 树时,将每个序列作为一个分支,初始时,对于表3中的第2个序列,在不考虑处理含有项集的序列模式情况下,如果将“D 3D 4D 2D 1”作为分支,D 3的节点则包含一个分支D 4;若以“D 3D 2D 4D 1”作为分支,D 3的节点则包含一个分支D 2,在这两种方法下,挖掘的结果分别是{D 4D 2D 1,D 3D 2D 1,D 3D 4D 2,D 3D 4D 1}和{D 4D 2D 1,D 3D 4D 2D 1,D 3D 4D 2,D 3D 4D 1}.根据文献[8]中241 复旦学报(自然科学版)第47卷 “顺序等价组”的定义,(D 2D 4)是相近组项集,OPC 树的分支需要按D 3(D 2D 4)D 1的顺序构建,因为(D 2D 4)是顺序无关的,即节点D 3中包含两个分支D 2和D 4,这样在后面剪枝过程“D 3D 4D 2”这个分支将会被作为不满足支持度阈值的分支而被剪枝.因此,在挖掘算法设计时,OP 2Cluster 构树方式可能会产生不同的结果模式甚至导致剪枝的不正确.算法建立在伪投影基础上,因此,当数据库较大时候,需要大量的磁盘操作,此时采用伪投影将达不到提高算法效率的作用,那么需要利用PrefixSpan (Prefix 2Projected Sequential pattern mining )算法[12]中的物理投影技术(Physical Project )进行处理.当数据存放在磁盘中时,计算哈希值d 需将序列编号和序列的偏移(offset )相结合.4 实验和结果分析我们选取两个真实数据集和一个人工数据集验证G en 2Cluster 算法的效率和挖掘结果.真实数据集(http :///geo/)分别来自Breast Tumor 表达数据集[13214](包含3226个探针probe 和22个组织)以及MicroRNA 表达数据集[15216](包括371个探针probe 和282个样本);仿真数据集是一个包含5000行和50列(维)的数据矩阵.G en 2Cluster 算法用C 实现,实验环境为CPU 900Hz ,内存512M ,Linux 系统.选取OP 2Cluster 算法作为对比算法,OP 2Cluster 算法可执行程序由文献[8]的作者提供,下载自文献[17].实验1 运行性能1)运行时间与簇支持度的关系G en 2Cluster 和OP 2Cluster 算法在我们选取的Breast Tumor 表达数据集的全部数据上运行,其时间与簇支持度关系的比较如图7所示(维支持度取20%).图7表示G en 2Cluster 和OP 2Cluster 运行时间都随簇支持度增大而减少,但总体G en 2Cluster 算法较优于OP 2Cluster 算法.2)运行时间与维支持度的关系实验测试G en 2Cluster 和OP 2Cluster 算法在Breast Tumor 数据集的全部数据上运行,其时间与维支持度关系的比较如图8所示(簇支持度取20%).由于OP 2Cluster 算法采用自顶向下的搜索策略,在挖掘过程中对OPC 树进行剪枝时,剪枝条件主要取决于用户定义的最小维数,当用户定义的维数阈值N (即维支持度)接近原始数据集中的维数时,能大量剪枝获得较快效率,然而当N 相对于数据集中维的个数较小时,剪枝条件难以满足,构造的OPC 树将增长加大,OP 2Cluster 算法效率受维支持度影响.而G en 2Cluster 算法是在挖掘得到所有长度维组合模式后再进行剪枝,G en 2Cluster 几乎不受维支持度影响.因此,在维支持度相对全局空间较小时,G en 2Cluster 算法也能具有较好的效率,这更符合一个感兴趣的生物过程通常只发生于少数条件中(即仅在相对原始空341 第2期熊 斌贝等:G en 2Cluster :一个基因表达数据的高维聚类算法 。
