||
算法名称:CC
论文名称:Cheng Y, Church GM. Biclusteringof expression data. In Philip Bourne, Michael Gribskov eds. proceeding of theeighth international conference on intelligent system for molecular biology.California,USA, 2000, 93~103
原文见附件
cc-ismb-Biclustering of expression data.pdf
论文摘要:
为了发现表达数据中的有低的均方残差的子矩阵,本文引入了一种有效的节点删除算法,通过对酵母和人的基因表达数据集的测试,它被显示出在找到共调控的模式是执行良好的。本文引入了关于基因和条件双聚类或者说同时聚类这一概念和从表达数据中知识发现的概念。由于该方法允许自动发现基于属性子集的相似性,同时对条件及基因进行聚类和对重叠分组(它提供了一种对有多重功能或者被多种因素调控的基因更好的表示方式),使得它克服了和传统聚类算法相关的一些问题。
论文内容概要:
本文首先分析了传统聚类算法处理表达数据时的缺点:首先是传统聚类算法在对基因聚类时为了衡量基因间的相似性要利用基因在所有条件下的表达水平,也就是说对所有的条件给予相同的权重;或者是在对实验条件聚类时要利用所有基因在该条件下的表达水平,也就是给所有的基因同样的权重,这种对所有基因或条件同等对待的方法使得不能发现表达矩阵数据中的所有相似的基因组或条件组。第二是因为传统的聚类算法将基因只能分在一个聚类中从而人为的认定每一个基因只有单一的功能,然而这是和实际的情况冲突的,现实中大量基因承担了在不同的条件下或时间下承担了不同的功能,也就是具有不同的通路。
基于上述传统聚类算法的缺点,在本文中提出了一个双聚类的概念,双聚类就是指具有按高度相似性的一组基因子集和一组条件子集。随后作者引入了均方残差(mean square residue,MSR)作为这种相似性的度量准则,并进行了相关的定义。这样从理论上指明了寻找双聚类的过程就是搜索表达矩阵找到使得MSR最小的所有子矩阵的过程。随后作者指出这样的一个最优的寻找过程等价于在一个二分图中寻找最大二分图极大团问题,并且该问题已经被证明是NP难的。但随后作者也指出在现实分析中并不需要搜索到最大的最优的双聚类,我们只要找到在一些特定条件下的一组基因具有共同上调或下调就行了。
随后本文对MSR进行了严格的数学定义,并证明了寻找最大的低于指定阈值的双聚类是NP难的。然而由于要找到的双聚类并不需要是最大的,所以本方使用贪心算法给出了最基本的寻找双聚类的算法-算法0。算法0简述如下:
算法0 (蛮力删除和增加算法)
输入:一个实值矩阵,一个最大可接受的均方残差值。
输出:一个均方残差不大于的用行集和列集表示的-双聚类。
初始化:行集和列集分别用整个表达矩阵的基因集和条件集来初始化,即:。
迭代:
1. 计算增加或删除任一行或列后得到的子矩阵的均方残差,选择相对原来均方残差来说减少最快的哪个操作,如果没有一个操作使得均方残差降低,或者,就返回
随后分析了算法的复杂度是,其中和分别是表达矩阵的行数和列数。接下来对算法0进行了优化提出了时间复杂度为的算法1,其详细内容如下:
算法1 (单点删除)
输入:一个实值矩阵,一个最大可接受的均方残差值。
输出:一个均方残差不大于的用行集和列集表示的-双聚类。
初始化:行集和列集分别用整个表达矩阵的基因集和条件集来初始化,即:。
迭代:
1.对双聚类对应的行集分别计算其行平均值,,对其列集分别计算其列平均值,,计算其全体平均值,并计算其均方残差。如果,则返回双聚类。
2. 在行集中寻找使得最大的行,在列集中寻找使得最大的列,经比较后得出二者当中的最大值所对应的行或列,并在该双聚类删除这个最大值所对应的行或列后更新行集和列集。
并给出了严格的数学证明(不过要注意的这些数学证明仅是对相似准则为MSR的时候才成立,换成其它相似度量准则的话就要重新证明了)。
由于在算法1中每次只能删除表达矩阵中的一行或一列,使得算法搜索过程较慢,为了找到提高搜索速度,本文随后又提出了多点删除算法2并给出了数学证明,详细步骤如下:
算法2(多点删除)
输入:一个实值矩阵,一个最大可接受的均方残差值。一个多点删除的阈值。
输出:一个均方残差不大于的用行集和列集表示的-双聚类。
初始化:行集和列集分别用整个表达矩阵的基因集和条件集来初始化,即:。
迭代:
1.对双聚类对应的行集分别计算其行平均值,,对其列集分别计算其列平均值,,计算其全体平均值,并计算其均方残差。如果,则返回双聚类。
2.删除双聚类中所有满足如下条件的行:。
3重新计算双聚类中每列的列平均值,和全体平均值以及均方残差。
4.删除双聚类中所有满足如下条件的列:。
5.如果在本次迭代中如果没有满足上述的条件行或列,则调用算法1.
随后本文分析了进行节点删除算法得到的双聚类可以增加特定的行或列而使得MSR不增加从而尽可能的得到较大的双聚类,并进行了相关的数学证明,提出了节点增加算法3:
算法3(节点增加)
输入:一个实值矩阵,和一个用和表示的双聚类
输出:一个用和表示的双聚类,其中,,并且满足。
迭代:
1.对双聚类中所有的行计算其行平均值,对其中所有的列计算列平均值,以及全体平均值和其对应的均方残差值。
2.把满足如下条件的列集和都添加到双聚类的列集中。
3.重新计算双聚类中每行的行平均值,整体平均值及其均方残差值。
4.把满足如下条件的行集和都添加到双聚类的行集中。
5.对不在双聚类行集中的每行,如果满足如下条件,也添加到双聚类的行集中。
6.如果没有行或列可添加,则把最终的和作为和返回。
最后为了找到给定数量的双聚类,论文整合了前面的算法给出了发现指定数量的双聚类算法4,其描述如下:
算法4(找出给定数目的双聚类)
输入:可能有缺失值的实值矩阵,用于多点删除的参数,最大可接受的均方残差值和要找的双聚类数目。
输出:中的个双聚类。
初始化:中的缺失值用随机数来代替,这些随机数取值范围是中非空值的取值范围。 是的一个副本。
迭代(次):
1. ,和作为输入参数来调用多点删除算法2。如果行或列的个数太小(小于100)就不再针对行或列执行多点删除算法2,这得到的矩阵是。
2.(算法2的第五步)和作为输入参数来调用单点删除算法1,经单点删除算法得到矩阵。
3. 和作为输入参数调用算法3,得到矩阵。
4.返回,并把在又在中的元素用随机数代替。
在算法4中由于算法执行的确定性,所以为了防止多次运行搜索到的都是基本相同的双聚类,对找到的双聚类用随机数进行覆盖并采用酵母数据集和人类B细胞数据集对算法进行了测试并和传统聚类算法结果进行了比较。
论文结论:
双聚类算法相对单聚类来说有好几个明显的优势。首先是双聚类自动地选择具有较一致的基因和条件,丢弃代表随机的噪音。这提供了一个方法来处理缺失数据和不准确的数据。
第二,双聚类基于一个依赖于应用背景的相似性度量标准来分类的,而这个标准是根据属性的子集来定义的。它不仅发现分组,而且也能发现分组适用的背景,在一定程度上,这二者之间是不可分隔的且可以交换的,这是双聚类算法和先单聚类列再单聚类行的算法的主要区别。
大多数表达矩阵来自于或多或少的完整的基因集,但其可能的条件是非常少的。任何基于可用条件的基因的相似性度量标准变得依赖于背景的。像这种基于准则的基因单聚类是没有双聚类算法那么有代表性。
第三,双聚类算法允许行和列被包含在多个双聚类中,从而允许一个基因或条件被多个功能分类所确定。这附加的灵活性正确的反映了在组织样本和实验条件下基因功能多样性和重叠因素这一事实。
通过证明该问题是一个NP难问题,我们尽力证明提出的算法的有效性和贪婪性。但由于问题的本质是NP难的,这就意味着有相当数量的具有很好度量标准的双聚类不能被任何有效的算法发现。和大多数有效的传统聚类算法一样,可以说最佳的双聚类能在大多数情况下能发现,但不能总在所在的情况下都能发现。
论文的创新之处:
1, 提出了双聚类的概念并结合贪心算法给出了相应的算法。
2, 提出了MSR作为基因相似性的衡量标准。
3, 对缺失数据的处理采用了随机数代替。
4, 为了防止找到重复的双聚类,采用了随机数来屏蔽已经找到的双聚类
5, 提出了使用双聚类的MSR和体积作为衡量双聚类算法结果的标准。
论文的不足之处:
1, 防止重复的策略会带来更大的随机干扰效应。
2, 很难发现重叠的双聚类。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-3-29 17:14
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社