Corrupted Cliques 与 CAST 算法

快速概览

基因表达数据常含噪声，导致距离图偏离理想的团图（Clique Graph）结构。Corrupted Cliques 问题研究如何用最少的边增删恢复团图结构，CAST 算法是一种实用的启发式解决方案。

理解聚类的核心质量标准：同质性（Homogeneity）与分离性（Separation）
掌握团图（Clique Graph）作为理想聚类结果的数学定义
了解 Corrupted Cliques 问题的计算复杂性（NP-hard）
学习 CAST 算法通过"亲和力"搜索构建稳健簇的逻辑

所属板块 分析方向与案例

把基础对象与算法方法重新放回真实分析任务与工作流。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

1. 要解决什么生物信息学问题？

在基因表达分析中，聚类（Clustering）的目标是将具有相似表达模式的基因归为一类。Corrupted Cliques 问题和 CAST 算法要解决的核心问题是：

当基因表达数据中存在实验噪声时，如何将基因可靠地分组为生物学上有意义的簇？

传统的聚类算法（如层次聚类和 k-means）在面对含噪声的高维基因表达数据时，可能会产生不稳定或不准确的结果。Corrupted Cliques 问题为这一挑战提供了一个图论框架，而 CAST 算法则是一个针对该框架设计的实用解决方案。

2. 输入与输出

输入

一个 $n \times m$ 的基因表达矩阵 $E$ ，其中 $n$ 是基因数量， $m$ 是实验条件（如时间点或组织类型）数量。
一个距离阈值 $\theta$ ，用于定义”相似”的边界。
一个距离度量函数 $d$ （如欧几里得距离、Pearson 相关系数）。

输出

基因的一个划分 $\{C_1, C_2, \ldots, C_k\}$ ，其中每个 $C_i$ 是一个簇。
簇的数量 $k$ 由算法自动确定。

3. 核心思想与数学模型

聚类的直觉：同质性与分离性

评价一个聚类好坏有两个核心直觉：

同质性（Homogeneity）：同一个簇内的成员应该尽可能相似。
分离性（Separation）：不同簇的成员应该尽可能不同。

距离图与理想聚类

我们将基因表示为图中的顶点。如果两个基因的表达距离小于某个阈值 $\theta$ ，我们就连一条边。

理想状态：图应该是 团图（Clique Graph），即每个连通分量都是一个完全图（所有点两两相连），且不同连通分量之间没有边。
现实噪声：由于实验误差，原本相似的基因可能没连上边（缺失边），原本不相关的基因可能连上了边（错误边）。

形式化地，给定图 $G = (V, E)$ ，如果 $G$ 满足以下条件，则称其为团图：

每个连通分量都是完全图（团）。
不同连通分量之间没有边。

团图是最理想的聚类结果——每个团对应一个簇，团内所有基因两两相似，不同团之间没有交叉相似性。

4. Corrupted Cliques 问题

问题定义

Corrupted Cliques Problem 的定义是：给定一个由于噪声而”损坏”的图 $G$ ，通过最少次数的添加边或删除边操作，将其修复为一个完美的团图。

形式化地： $\min_{H} |E(G) \triangle E(H)|$

其中 $H$ 是一个团图， $E(G) \triangle E(H)$ 表示对称差（需要增删的边的总数）。

计算复杂性

复杂性：该问题被证明是 NP-完全（NP-complete） 的。这意味着不存在已知的多项式时间精确算法（除非 P = NP）。
意义：这说明在存在噪声的情况下，寻找理论上的”最优”聚类在计算上是极其困难的。因此，我们需要依赖启发式算法（如 CAST）来寻找近似解。

与图编辑距离的关系

Corrupted Cliques 问题可以看作是图编辑距离（Graph Edit Distance） 的一个特例：给定一个图，找到与它”最接近”的团图。图编辑距离的一般形式是 NP-难的，即使限制目标图为团图，问题仍然是 NP-完全的。

5. CAST 算法

为了处理大规模基因表达数据，Ben-Dor, Shamir 和 Yakhini 提出了 CAST (Cluster Affinity Search Technique) 算法。

核心概念：亲和力（Affinity）

基因 $i$ 对簇 $C$ 的亲和力定义为它与簇中所有成员的平均距离：

$\text{Affinity}(i, C) = \frac{1}{|C|} \sum_{j \in C} d(i, j)$

如果 $\text{Affinity}(i, C) \leq \theta$ ，我们认为该基因与簇是 Close 的（足够相似）。
如果 $\text{Affinity}(i, C) > \theta$ ，则该基因与簇是 Distant 的。

算法伪代码

算法 CAST(D, theta)
输入：n x n 距离矩阵 D，阈值 theta
输出：簇的集合 {C_1, C_2, ..., C_k}

1. S = {所有基因}
2. Clusters = {}
3. while S 不为空:
4.     C = {}
5.     选择 S 中度数最高的基因 v 作为种子，C = {v}
6.     changed = True
7.     while changed:
8.         changed = False
9.         for each gene i in S \ C:
10.            if Affinity(i, C) <= theta:
11.                C = C ∪ {i}
12.                changed = True
13.        for each gene j in C:
14.            if Affinity(j, C \ {j}) > theta:
15.                C = C \ {j}
16.                changed = True
17.    Clusters = Clusters ∪ {C}
18.    S = S \ C
19. return Clusters

算法逻辑

CAST 采用”边建边修”的策略：

选种：从剩余基因中选一个度数最高的作为新簇的种子。选择高度数基因作为种子是为了确保初始簇具有较高的”吸引力”。
拉人（Add）：只要存在与当前簇 Close 的基因，就将其加入簇中。
踢人（Remove）：加入新成员后，重新检查。如果某个成员因为新人的加入而导致它与簇的平均亲和力降至阈值以下（变得 Distant），则将其踢出。
收敛：直到簇成员不再变化，完成一个簇的构建，并从总集中移除这些基因。

为什么需要”踢人”步骤？

“踢人”步骤是 CAST 算法区别于简单贪心聚类的关键。当一个新基因被加入簇后，它可能会改变簇的”重心”，使得原来的一些成员变得不再 Close。如果不进行踢人操作，簇的质量会逐渐下降。踢人步骤保证了每个簇中的基因与簇的整体亲和力始终满足阈值条件。

6. Worked Example

假设有 5 个基因，距离矩阵如下（ $\theta = 3$ ）：

	$g_1$	$g_2$	$g_3$	$g_4$	$g_5$
$g_1$	0	1	2	8	9
$g_2$	1	0	2	7	8
$g_3$	2	2	0	7	9
$g_4$	8	7	7	0	1
$g_5$	9	8	9	1	0

构建第一个簇：选择度数最高的基因 $g_1$ （度数 2）作为种子。

第一轮拉人：

$\text{Affinity}(g_2, \{g_1\}) = 1 \leq 3$ ，加入。 $C = \{g_1, g_2\}$ 。
$\text{Affinity}(g_3, \{g_1, g_2\}) = \frac{2+2}{2} = 2 \leq 3$ ，加入。 $C = \{g_1, g_2, g_3\}$ 。
$\text{Affinity}(g_4, C) = \frac{8+7+7}{3} = 7.33 > 3$ ，不加入。
$\text{Affinity}(g_5, C) = \frac{9+8+9}{3} = 8.67 > 3$ ，不加入。

第一轮踢人：所有成员的亲和力均满足条件，保留。

$C_1 = \{g_1, g_2, g_3\}$ ， $S = \{g_4, g_5\}$ 。

构建第二个簇：种子选 $g_4$ ， $\text{Affinity}(g_5, \{g_4\}) = 1 \leq 3$ ，加入。 $C_2 = \{g_4, g_5\}$ 。

结果： $\{g_1, g_2, g_3\}$ 和 $\{g_4, g_5\}$ ，与距离矩阵中的自然分组一致。

7. 复杂度与适用前提

时间复杂度

最坏时间复杂度： $O(n^3)$ 。
实际中通常远快于此，因为大多数基因在几轮内就会被分配。

空间复杂度

存储距离矩阵： $O(n^2)$ 。

适用前提

数据中存在”自然的”分组结构。
阈值 $\theta$ 的选择合理。

8. CAST 的优势与局限

优点	局限
无需预设 k：不需要提前知道有多少个簇。	对阈值敏感： $\theta$ 的选择极大地影响结果。
稳健性：能比层次聚类更好地处理基因表达中的噪声。	不保证最优：作为启发式算法，结果依赖初始种子的选择。
直觉清晰：基于亲和力的概念易于理解和调参。	无法处理重叠聚类：每个基因只能属于一个簇。

9. 与其他聚类方法的对比

特性	CAST	k-means	层次聚类
需要预设 k	否	是	否
距离度量	任意	欧几里得	任意
噪声鲁棒性	较好	差	中等
时间复杂度	$O(n^3)$ 最坏	$O(n \cdot k \cdot d)$	$O(n^2)$

11. 与真实工具的连接

CLUSTER (Eisen Lab): 经典的基因表达聚类软件包，实现了包括 CAST 在内的多种聚类算法。最初为微阵列数据分析设计。
R 语言 cluster 包: 提供了多种聚类算法的实现，可以结合 CAST 的思想使用 pam 等方法。
WGCNA: 加权基因共表达网络分析工具。虽然不直接实现 CAST，但其将基因表达数据转化为网络图并进行模块检测的思想与 CAST 的图论框架高度一致。