什么是双聚类？

自从基因芯片技术产生以来，大量的生物数据需要分析，这些数据大多规格化之后以矩阵的形式表示和存储，俗称 DNA 微阵列矩阵或基因表达数据矩阵。一般的聚类是根据数据的全部属性将数据聚类，这种聚类方式称为传统聚类。传统聚类只能寻找全局信息，无法找到局部信息，而大量的生物学信息就隐藏在这些局部信息中。为了寻找在基因芯片数据中隐藏的局部信息，人们提出了双聚类的概念。

双聚类算法是同时对行和列进行聚类，目的是为了找出基因集在条件集下有紧密联系的子矩阵，这样的子矩阵就称为双聚类。

传统聚类和双聚类的区别

图1 普通聚类和双聚类的比较

上图是一个基因表达矩阵的普通聚类（左一、左二）和双聚类（右图）对比。微阵列数据允许同时检测在不同条件下的不同基因行为。对于一系列条件，每一基因都有对应的表达谱（左一），这个表达谱可以被视为这一基因对应这一系列条件的属性表达谱。相反，在同一条件下，不同基因的表达水平所形成的向量或集合被称为条件表达谱（左二）。一个 gene cluster（左一）必须包括所有的列，一个 condition cluster（左二）必须包括所有的行，而一个双聚类 Biclusters 对应的是行和列的任意子集。从图中，我们也可以看出在双聚类的算法中，基因或条件既可以属于多个簇（双聚类），也可以不在任何簇中，簇间也可以存在重叠区。

Unibic双聚类算法

因为传统的单聚类算法应用到基因表达数据中得到的结果通常反映了所有条件下部分基因组的相关性，或部分条件组下的所有基因的相关性，但是大部分基因通常只在部分条件集下具有表达相关性。在基因表达分析中，具有相似表达趋势而非相似表达值的基因在生物学过程中表现出协同调控，即变化相关的双聚类对于生物学更有意义。因此，双聚类不关心某一基因的具体数值，而是更关心某些基因是否在某些条件下呈现共同变化趋势。所以采用双聚类能够专注于寻找趋势一致的双聚类，从而找到对生物学更有意义的基因，即关键基因。

图2 Unibic 双聚类算法流程图

上图为 Unibic 双聚类算法的流程图。Unibic 算法的基本思路是：首先将基因表达数据矩阵作为输入，构建索引矩阵，然后随机挑选任意两行并求其最长的公共序列长度，若两行之间的公共序列长度满足预先设置的阈值，则得到了初始的双聚类种子。紧接着对初始的双聚类种子进行扩展，得到完整的双聚类。

Unibic 双聚类算法具体流程

1、构造索引矩阵

不同算法初始双聚类的设定不一样，有的是直接采用整个原始矩阵（基因表达数据矩阵），然后通过删减行列不断靠近目标函数值的方式来得到最终的双聚类，如 CC 双聚类算法。为了反映出原始矩阵数值的相对变化趋势，可构造原始矩阵对应的索引矩阵来找到变化相关的双聚类种子。下图是我从某文拿到的原始矩阵数据：

图3 基因表达数据矩阵

构造索引矩阵的原因：（1）索引矩阵可以反应数值大小的变化。（2）求索引矩阵行对之间的最长公共子序列可以得到基因之间具有顺序一致表达的最大条件集。

求索引矩阵行对之间的最长公共序列的原因：这里可以将两个基因行之间的最长公共序列看做两个基因的相似度，那么如果最长公共序列短，则认为这两个基因仅在很少的条件下处于共同变化的情况，则他们的相关性低；反之，如果这两个基因行间的最长公共序列长，则说明他们的相似度高。如果它们在很多条件下的表达值都处于同增同减的情况，那么它们很可能属于同一个趋势一致的双聚类。下图是图3对应的索引矩阵：

图4 索引矩阵

索引矩阵的求法：

设 $A[I,J]$ 为原始矩阵， $Y[I,J]$ 为索引矩阵，其中 $Y[i,j] = r$ ，当且仅当 $A[i,j]$ 是A中第 $i$ 行中第 $r$ 小的元素，即按表达值先升序排序，表达值的排列号作为表达值在索引矩阵所对应的数值。

图5 原始矩阵

（1）以第一行为例，我们先将第一行 $a_{1j}$ 的元素进行排序；（2）取排列后元素的列下标作为索引矩阵的数值，构造索引矩阵。然后我们就能得到如图4所示的索引矩阵。构造索引矩阵的方法如图6所示：

图6 构造索引矩阵的方法

2、获取双聚类种子

得到索引矩阵之后，我们再任意选择两行并通过 LCS 算法计算两行之间的最长公共序列，得到一个双聚类种子（如图7所示），这里我们就选择第一行和第二行。这里可以看出我们的基因（行）是呈现单调递增的趋势，也就是严格保序。

图7 双聚类种子

3、将种子扩增为最终双聚类种子

因为目前得到的种子是从索引矩阵中任取两行求得的，有可能会漏掉与种子中的基因同样满足最长公共子序列长度且超过显著长度的基因。所以，我们要遍历索引矩阵中除初始种子两行之外的所有行，求出与种子中第一个基因所对应的行的最长公共序列，挑选其中保持序列长度最长的行所对应的基因，将这个基因添加到种子基因集合中构成最终双聚类种子。也就是说，最终的双聚类种子是由3个基因（3行）组成，且满足严格保序。可能的情况如下图所示：

图8 最终双聚类种子的索引矩阵

4、扩展双聚类

虽然最终的双聚类种子是高度满足趋势一致的双聚类，但是双聚类中基因和条件的数量太少，而双聚类需要一定的行列数支持。为了扩展双聚类，可以通过降低一致度来添加相关行或者列，最后使得双聚类表达值呈现大致一样的变化趋势。

行的扩展

首先，作者以贪婪的方式一次加一行，直到保持序列的子矩阵的行数大于列数。这时候的双聚类依然是严格保序的。如图9所示：

图9 行的扩展

列的扩展

在扩展行之后，得到依旧严格保序的双聚类的基础上，满足错误率 $r≤0.3$ （这里的 $r$ 个人理解是指添加列之后双聚类保持趋势的状态， $r$ 越接近0表示双聚类更严格保序， $r$ 越接近1表示双聚类不保序）的情况下，一次重复添加一个新的列，直到没有新的列为止。此时得到的双聚类是近似保持趋势的双聚类。如图10所示：

图10 列的扩展

在列扩展之后，因为之前的行数并未全部扩展完，所以还需要继续对行扩展，满足错误率 $r≤0.15$ 的条件，直到没有可用的行。这时就得到一个完整的双聚类。这个双聚类是满足近似保持趋势的。

参考文献

Wang Z , Li G , Robinson R W , et al. UniBic: Sequential row-based biclustering algorithm for analysis of gene expression data[J]. Rep, 2016, 6(1):23466.

【双聚类】Unibic双聚类算法