2 Method

下面按 2 METHODS 的五个小节逐节详解。先给一张“方法总览图”帮助定位：

IsoRankN 两阶段流水线：

阶段1：成对打分（2.1）
  对每对网络 (G_i, G_m) 跑原版 IsoRank
  → 得到每对跨物种蛋白 (v_i, v_j) 的功能相似分数 R_ij
  → 构建“功能相似图”：k 部完全加权图

阶段2：找跨物种簇（2.2–2.5）
  对每个蛋白 v：
    2.2 取星 S_v = 与 v 高权相连的邻居
    2.3 在 S_v 上做 Personalized PageRank 局部谱划分 → 低 conductance 子集 S_v*
    2.4 合并满足“互为邻居”条件的星
    2.5 按顺序对所有蛋白重复，直到所有蛋白被分配

---

2.1 Functional similarity graph（功能相似图）

2.1.1 核心思想

The central idea of IsoRankN is to build a multiple network alignment by local partitioning of the graph of pairwise functional similarity scores.

中文理解：
IsoRankN 不直接在所有网络上一次性求解多对齐，而是：

1. 先算每一对跨物种蛋白之间的功能相似分数；
2. 把这些分数组织成一个加权 k 部完全图；
3. 在这个图上做局部划分，得到跨物种蛋白簇。

这样做把“多网络组合爆炸”分解为“成对打分 + 图上局部聚类”，复杂度大幅下降。

---

2.1.2 IsoRank 的基本原理

IsoRank works on the principle that if two nodes of different networks are aligned, then their neighbors should be aligned as well.

中文理解：
如果物种 A 的蛋白 $v_i$ 与物种 B 的蛋白 $v_j$ 功能对应，那么 $v_i$ 的相互作用邻居也应该与 $v_j$ 的相互作用邻居功能对应。这就是“邻居也要对齐”的拓扑保守性原则。

公式：

$$R_{ij} = \sum_{v_u \in N(v_i)} \sum_{v_w \in N(v_j)} \frac{1}{|N(v_u)||N(v_w)|} R_{uw}$$

符号解释：

• $R_{ij}$：蛋白 $v_i$ 与 $v_j$ 的功能相似分数；
• $N(v_i)$：$v_i$ 在自己网络内的邻居集合；
• 求和遍历 $v_i$ 的每个邻居 $v_u$ 和 $v_j$ 的每个邻居 $v_w$；
• 分母 $|N(v_u)||N(v_w)|$ 做归一化，防止高度节点主导；
• 右边 $R_{uw}$ 是邻居对之间的相似分数。

直观： 一对蛋白的相似度，等于它们邻居对相似度的加权平均。这是一个自洽方程，可以看成两个网络直积图上的随机游走稳态分布。

This can also be viewed as the steady- state distribution of a random walk on the direct product of the two networks.

中文理解： 在“乘积图”上随机游走：同时从两个网络各选一个节点，每一步同时跳到各自邻居。长期停留在某节点对上的概率，就是 $R_{ij}$。

---

2.1.3 融合序列同源性

仅有拓扑还不够，还要结合序列相似性。IsoRank 用参数化平均：

$$R = \alpha AR + (1-\alpha)E, \quad 0 \le \alpha \le 1$$

符号解释：

• $R$：所有成对功能相似分数组成的向量；
• $A$：网络拓扑的转移矩阵（乘积图上的归一化邻接矩阵）；
• $E$：序列同源性向量（BLAST bit-score 归一化）；
• $\alpha$：拓扑相似性与序列相似性的权衡参数；
• $(1-\alpha)E$：把序列相似性作为“重启/先验”注入。

理解： 这类似 PageRank 的“随机跳转”项：以概率 $\alpha$ 按网络拓扑走，以概率 $1-\alpha$ 回到序列相似性给出的先验。用幂法求唯一正解 $R$。

论文实验取 $\alpha = 0.6$，即拓扑占 60%，序列占 40%。

---

2.1.4 从成对分数到功能相似图

Specifically, given $k$ PPI networks $G_1, G_2, \ldots, G_k$ we first compute the functional similarity scores of every pair of cross- species proteins $(v_i, v_j) \in (G_i, G_m)$. This is done using the original IsoRank algorithm (Box 1), but without the final step of greedily selecting an alignment.

关键点： IsoRankN 不用原版 IsoRank 最后的贪心对齐步骤。原版 IsoRank 拿到 $R$ 后贪心选对齐，耗时且只给一个离散映射；IsoRankN 保留连续的 $R$ 分数，用于构建图。

The result is a functional similarity graph, a weighted complete $k$ - partite graph on the $k$ sets of proteins, where each edge is weighted by its functional similarity score.

功能相似图定义：

• 顶点：所有 $k$ 个网络中的全部蛋白；
• 部：每个物种是一个部；
• 边：只连不同物种的蛋白对（部内无边，所以是 k 部图）；
• 任意两个不同物种的蛋白之间都有边（完全图）；
• 边权：IsoRank 分数 $R_{ij}$。

注意： 部内没有边，所以同一物种的两个蛋白在功能相似图中不直接相连。这就是后文 2.4 “star spread 不会把同网络蛋白放进同一簇”的原因。

---

2.1.5 为什么不是直接找最大加权 clique？

If the PPI networks were complete and exact, the multiple alignment problem would simply be to find maximally weighted cliques. As the networks are not, we introduce the star spread method to find highly similar near cliques, which yields a multiple alignment.

中文理解：

• 理想情况：如果 PPI 网络完整且准确，功能相似图中一个跨物种簇应该是一个最大加权 clique——每两个跨物种蛋白都高相似。
• 现实：PPI 数据有噪声、不完整，严格的 clique 几乎不存在。
• 因此作者找近 clique / 高权重邻域子集，即“star spread”。

In addition, in contrast to the seed- path extension method used by NetworkBLAST- M, our method is similar to the star aligned approach in multiple sequence alignment introduced by Lipman et al. (1989) and CLUSTAL W (Thompson et al., 1994).

类比： 多序列比对里有“星形比对”：选一个中心序列，其他序列都与它比对。IsoRankN 的 star spread 类似：选一个中心蛋白，找与它高权相连的跨物种蛋白子集。不同之处是这里用谱划分而非简单阈值。

---

2.2 Star spread（星形扩散）

2.2.1 什么是“星”$S_v$

We first compute, for every protein $v$ in a chosen species, every neighbor connected to $v$ by an edge with weight greater than a threshold; this is the star, $S_v$ of the protein (Fig. 1a).

对选定物种中的每个蛋白 $v$，定义它的星：

$$S_v = \{ v_j \in N(v) \mid w(v, v_j) \ge \beta \max_{j} \{ w(v, v_j) \} \}$$

符号解释：

• $N(v)$：功能相似图中 $v$ 的邻居（因为图是 k 部完全图，邻居就是所有其他物种的蛋白）；
• $w(v, v_j)$：边权，即 IsoRank 功能相似分数；
• $\beta$：相对阈值，论文取 0.01；
• $\max_j \{ w(v, v_j) \}$：$v$ 的最强边权。

理解： 保留与 $v$ 相似度不低于“最强边权的 1%”的邻居。用相对阈值而非绝对阈值，可适应不同物种、不同蛋白的分数尺度差异。

Fig. 1a 例子：以酵母蛋白 YDR001C 为中心，星包含人、蝇、蠕虫、鼠中与它高权相连的蛋白。

---

2.2.2 为什么要“扩散/划分”星

We greedily order the proteins $v$ by the total weight of $S_v$ and for each find the subset $S_v^* \subset S_v$ such that $S_v^*$ is a highly weighted neighborhood of $v$ (Fig. 1b).

问题： 星 $S_v$ 只是“与 $v$ 高权相连的邻居集合”，但邻居彼此之间可能并不高相似。一个真正的跨物种功能簇，应该不仅每个成员与 $v$ 相似，成员之间也彼此相似。

目标： 从 $S_v$ 中找子集 $S_v^*$，使它是一个高权重邻域，即内部连接紧密、与外部连接稀疏的低 conductance 集合。

This is done using a spectral local graph partitioning algorithm with approximate Personalized PageRank vectors, similar to the PageRank- Nibble algorithm.

方法： 用近似 Personalized PageRank 的局部图划分（详见 2.3）。

The resulting $S_v^*$ represents a functionally conserved interaction cluster, a set of network- aligned proteins.

输出： $S_v^*$ 就是一个跨物种保守相互作用簇，即一组网络对齐的蛋白。

---

2.2.3 处理顺序与重复

This is repeated for every protein in all species not already assigned to an $S_v^*$, yielding assignments for all vertices.

流程：

1. 按 $S_v$ 的总边权从大到小给蛋白排序；
2. 依次处理每个尚未分配的蛋白 $v$；
3. 对 $v$ 的星 $S_v$ 做谱划分，得到 $S_v^*$；
4. 把 $S_v^*$ 中尚未分配的蛋白分配给这个簇；
5. 重复，直到所有蛋白都被分配。

While it is not clear exactly how the order of vertex choice affects the results, this ordering performs better empirically than others we have tried, including random ordering.

理解： 先处理“星总权重高”的蛋白，因为它们的邻域信息更可靠，先形成高质量簇。作者承认顺序影响结果，但经验上按总权重排序优于随机顺序。物种顺序在 3 RESULTS 的 Ordering 部分讨论。

---

2.3 Spectral partitioning（谱划分）

这是方法中最数学化的部分，核心是：用 Personalized PageRank 找包含 $v$ 的低 conductance 集。

2.3.1 为什么找低 conductance 集而不是最大加权 clique

The main algorithmic challenge in obtaining functionally conserved interaction clusters $S_v^s$ is uncertainly introduced by the incomplete and inaccurate PPI network data. Thus instead of finding a maximally weighted clique containing $v$ we find a low- conductance set containing $v$

理解：

• 严格 clique 对噪声太敏感：少一条边或分数偏低，clique 就不成立；
• 低 conductance 集允许“近似 clique”：内部边多、外部边少，但不要求完美；
• 这与谱方法误差容忍的特性一致。

---

2.3.2 Conductance 定义

The conductance, $\Phi(S)$ of a subset $S$ of a graph $G$ is the ratio of the size of the edge cut to separate $S$ to the number of edges in the larger of the two remaining sets, providing a very natural measure of 'clusterness' of a subset of vertices.

公式：

$$\Phi(S) = \frac{\sigma(S)}{\min[\mathrm{vol}(S),\, 2m - \mathrm{vol}(S)]}$$

其中：

$$\sigma(S) = |\{(v_x, v_y) : v_x \in S, v_y \notin S\}|$$ $$\mathrm{vol}(S) = \sum_{i} \mathrm{deg}(v_i)$$

$m$ 是图 $G$ 的边数。

符号解释：

• $\sigma(S)$：割边数，即从 $S$ 连到 $S$ 外面的边数；
• $\mathrm{vol}(S)$：$S$ 的体积，即 $S$ 中所有节点度数之和；
• $2m - \mathrm{vol}(S)$：补集的体积（无向图中所有节点度数和为 $2m$）；
• 分母取较小体积，避免偏向小集合或大集合。

直观： conductance 越小，$S$ 越“像簇”——内部连接多、外部连接少。$\Phi(S)$ 归一化后，不同大小集合可比。

---

2.3.3 Personalized PageRank 向量

Anderson et al. (2006) showed that a low- conductance set containing $v$ can be computed efficiently via the personalized PageRank vector of $v$.

核心结论： 不需要对整个图做全局划分，只需从 $v$ 出发做局部随机游走，就能高效找到包含 $v$ 的低 conductance 集。这正是 PageRank-Nibble 的思想。

A personalized PageRank vector $Pr(\gamma, v)$ is the stationary distribution of the random walk on $S_v$ in which at every step, with probability $\gamma$ the walk 'teleports' back to $v$ and otherwise performs a lazy random walk with transition probabilities proportional to $R$.

随机游走解释：

• 当前在某个节点；
• 每一步以概率 $\gamma$ “传送”回起点 $v$；
• 否则以 $1-\gamma$ 做懒惰随机游走：以 1/2 概率不动，以 1/2 概率按边权比例跳到邻居。

公式：

$$Pr(\gamma, v) = \gamma \chi_v + (1-\gamma) Pr(\gamma, v) W$$

其中：

$$W = \frac{1}{2}(I + D^{-1}R)$$

符号解释：

• $\gamma \in (0,1]$：传送概率/重启概率；
• $\chi_v(x) = \delta_{x,v}$：指示向量，只在 $v$ 处为 1；
• $R$：成对交互分数矩阵（功能相似图的加权邻接矩阵）；
• $D$：$R$ 的列和构成的对角矩阵，用于归一化；
• $W$：懒惰随机游走转移矩阵；
• $I$：单位矩阵，对应“不动”的那 1/2 概率。

理解： Personalized PageRank 向量 $p$ 的每个分量 $p(x)$ 表示从 $v$ 出发、不断“回到 $v$”的随机游走长期停留在 $x$ 的概率。与 $v$ 连接紧密的节点会获得较高质量。传送概率 $\gamma$ 控制局部性：$\gamma$ 越大，越集中在 $v$ 附近；$\gamma$ 越小，扩散越远。

For the purposes of this article, we instead use an efficient approximation $p := Pr(\gamma, v)$ the details of which can be found in (Anderson et al., 2006).

实际实现： 不精确求解线性系统，而用 Anderson et al. (2006) 的近似算法，只对“质量高”的节点做推送，复杂度与输出集合大小相关，而非全图大小。这是 PageRank-Nibble 高效的关键。

---

2.3.4 从 PageRank 向量到最小 conductance 割

To compute the minimal conductance cut, we consider the sets $T_j^p = \{v_i \mid \frac{p(v_i)}{\sum_k R_k} \ge \frac{p(v_j)}{\sum_k R_k}\}$ or those vertices which contain at least as much of the mass of $p$ normalized by R.

中文理解： 把节点按“归一化 PageRank 质量”从大到小排序，取前若干名构成候选集合 $T_j^p$。

• $p(v_i)$：节点 $v_i$ 的 PageRank 质量；
• 分母 $\sum_k R_k$ 做归一化（原文写法可能有笔误，通常用度数或体积归一化）；
• $T_j^p$：质量不低于阈值（由 $v_j$ 的质量决定）的所有节点。

然后：

$$S_v^s = \min_j \Phi(T_j^p)$$

理解： 对所有可能的截断 $j$，计算候选集 $T_j^p$ 的 conductance，取 conductance 最小的那个作为 $S_v^s$。这就是“扫描割”（sweep cut）：PageRank 向量给出节点排序，扫描所有前缀，找 conductance 最小的前缀。

为什么有效： Anderson et al. (2006) 证明，Personalized PageRank 向量的扫描割能近似最优低 conductance 集，且只需局部计算。

---

2.3.5 本节小结

概念	作用
conductance $\Phi(S)$	衡量集合“像不像簇”
Personalized PageRank	从 $v$ 出发的局部随机游走稳态
懒惰随机游走 $W$	避免周期性，保证收敛
传送概率 $\gamma$	控制局部性
扫描割 $\min_j \Phi(T_j^p)$	从 PageRank 排序中选最优截断
近似算法	只处理高质量节点，高效

---

2.4 Star merging（星合并）

2.4.1 问题：star spread 不会把同网络蛋白放进同一簇

While highly efficient, the star spread method has the limitation of not assigning other members of the original network to the neighborhood $S_v$ and so $S_v^s$ by necessity does not contain any other proteins in the same network as $v$ even if it is appropriate to do so.

原因： 功能相似图是 k 部图，同一物种的蛋白之间没有边。因此以 $v$ 为中心的星 $S_v$ 只包含其他物种的蛋白；$S_v^s \subset S_v$ 自然也不含与 $v$ 同网络的蛋白。

后果： 如果两个同物种蛋白 $v_1, v_2$ 实际上是旁系同源（paralog），并且都应该与另一物种的同一组蛋白对齐，star spread 会把它们分到不同簇，导致本应合并的簇被拆开。

2.4.2 合并条件

For two stars, $S_{v_1}^s$ and $S_{v_2}^s$ where $v_1$ and $v_2$ are in the same PPI network, if every member of $S_{v_1}^s \setminus \{v_1\}$ has $v_2$ as a neighbor and vice versa, we merge $S_{v_1}^s$ and $S_{v_2}^s$

条件： 对同一 PPI 网络中的两个中心 $v_1, v_2$，如果：

• $S_{v_1}^s$ 中除 $v_1$ 外的每个成员都与 $v_2$ 相邻（即 $w(v_2, \cdot)$ 高）；
• 且 $S_{v_2}^s$ 中除 $v_2$ 外的每个成员都与 $v_1$ 相邻；

则合并 $S_{v_1}^s$ 和 $S_{v_2}^s$。

直观： 如果 $v_1$ 的簇成员都“认可” $v_2$，$v_2$ 的簇成员也都“认可” $v_1$，说明 $v_1$ 和 $v_2$ 功能冗余/旁系同源，应放在同一跨物种簇中。

2.5 算法步骤 (4) 给出更精确的阈值版本：

$$\forall v_i \in S_{v_2}^s \setminus \{v_2\}, \quad w(v_1, v_i) \ge \beta \max_j \{w(v_1, v_j)\}$$

且

$$\forall v_j \in S_{v_1}^s \setminus \{v_1\}, \quad w(v_2, v_j) \ge \beta \max_j \{w(v_2, v_j)\}$$

理解： 不是要求严格相邻（边权 > 0），而是要求边权不低于 $v_1$（或 $v_2$）最强边的 $\beta$ 比例。这延续了 star 定义的相对阈值思想，容忍噪声。

2.4.3 合并的意义

• 允许一个跨物种簇包含同一物种的多个旁系同源蛋白；
• 解决 k 部图部内无边导致的“同物种蛋白无法同簇”问题；
• 提高覆盖度，尤其对基因重复多的物种重要。

---

2.5 The IsoRankN algorithm（完整算法）

把前面所有步骤串起来。输入：$k$ 个 PPI 网络 $G_1, \ldots, G_k$，阈值 $\beta$。

Step 1：成对打分

Run the original IsoRank on every pair of networks to obtain scores $R_{ij}$ on all edges of the functional similarity graph.

对每一对网络跑原版 IsoRank（不求最终贪心对齐），得到功能相似图所有边的分数 $R_{ij}$。

输出： 加权 k 部完全图。

---

Step 2：计算每个蛋白的星

For every protein $v$ compute the star $S_v = \{v_j \in N(v) \mid w(v, v_j) \ge \beta \max_j \{w(v, v_j)\}\}$ where $N(v)$ is the neighborhood of $v$ in the functional similarity graph.

按 2.2 定义，对每个蛋白 $v$ 计算星 $S_v$，保留边权不低于 $v$ 最强边 $\beta$ 倍的邻居。

---

Step 3：按顺序谱划分星

Pick an arbitrary remaining PPI network $G_L$ and order the proteins $v \in G_L$ by the sum of edge weights in the induced graph on $S_v$. In order, excluding proteins already assigned to clusters, spectrally partition $S_v$ to obtain $S_v^s$

流程：

1. 选一个尚未处理完的 PPI 网络 $G_L$（物种顺序可调，见 RESULTS 的 Ordering）；
2. 对 $G_L$ 中每个蛋白 $v$，计算其星 $S_v$ 的诱导子图的总边权；
3. 按总边权从大到小排序；
4. 依次处理尚未分配的 $v$：
   • 在 $S_v$ 上做谱划分（2.3 的 Personalized PageRank + 扫描割），得到 $S_v^s$；
   • 将 $S_v^s$ 中尚未分配的蛋白分配到这个簇。

为什么按总边权排序： 总边权高说明 $v$ 的邻域信号强、更可靠，先形成高质量簇。

---

Step 4：星合并

Merge every pair of clusters $S_{v_1}^s$ and $S_{v_2}^s$ in which $\forall v_i \in S_{v_2}^s \setminus \{v_2\}, w(v_1, v_i) \ge \beta \max_j \{w(v_1, v_j)\}$ and $\forall v_j \in S_{v_1}^s \setminus \{v_1\}, w(v_2, v_j) \ge \beta \max_j \{w(v_2, v_j)\}$

按 2.4 的条件合并同一网络中中心蛋白不同的簇。合并后得到一个更大的跨物种簇，可包含同物种旁系同源。

---

Step 5：重复直到所有蛋白被分配

Repeat steps 3 and 4 until all proteins are assigned to a cluster.

终止条件： 所有蛋白都被分配到某个簇。

注意： 由于 star 只含跨物种邻居，且 star spread 以某个蛋白为中心，最终每个簇至少包含两个物种。论文明确指出：IsoRankN 不会在某一物种内单独找旁系同源，除非至少有一个其他物种的同源蛋白存在。

---

方法部分整体逻辑链

2.1 成对 IsoRank 打分
    ↓ 得到加权 k 部功能相似图
2.2 每个蛋白取星 S_v（相对阈值 β）
    ↓ 星只是高权邻居集合，还需内部紧密
2.3 在 S_v 上做 Personalized PageRank + 扫描割
    ↓ 得到低 conductance 子集 S_v^s（近 clique 簇）
2.4 合并同物种中心、互为邻居的簇
    ↓ 解决 k 部图部内无边问题，纳入旁系同源
2.5 按星总权重排序，迭代执行 2.2–2.4
    ↓ 输出所有蛋白的跨物种簇分配

---

关键公式速查

公式	含义
$R_{ij} = \sum_{\substack{v_u \in N(v_i) \\ v_w \in N(v_j)}} \frac{1}{\|N(v_u)\|\|N(v_w)\|} R_{uw}$	IsoRank 拓扑相似自洽方程
$R = \alpha AR + (1-\alpha)E$	拓扑与序列同源性的参数化平均
$S_v = \{v_j \in N(v) \mid w(v,v_j) \ge \beta \max_j w(v,v_j)\}$	星的定义
$\Phi(S) = \frac{\sigma(S)}{\min[\mathrm{vol}(S), 2m-\mathrm{vol}(S)]}$	conductance
$Pr(\gamma,v) = \gamma \chi_v + (1-\gamma) Pr(\gamma,v) W$	Personalized PageRank
$W = \frac{1}{2}(I + D^{-1}R)$	懒惰随机游走转移矩阵
$S_v^s = \min_j \Phi(T_j^p)$	扫描割选最小 conductance 前缀

---

方法部分的“设计哲学”总结

1. 用连续分数代替离散对齐：IsoRank 的 $R$ 是连续相似度，保留信息，避免早期贪心错误传播。
2. 用局部谱划分代替全局优化：Personalized PageRank 只从 $v$ 附近找簇，高效且适应网络大小差异。
3. 用低 conductance 代替严格 clique：容忍 PPI 数据噪声和不完整。
4. 用相对阈值 $\beta$ 代替绝对阈值：适应不同蛋白、不同物种的分数尺度。
5. 用星合并弥补 k 部图部内无边：允许同物种旁系同源进入同一簇。
6. 用排序启发式处理重叠：先处理信号强的蛋白，减少分配冲突。

如果你愿意，下一步我们可以继续精读 3 RESULTS，重点解释 Table 1 的熵指标、Table 2 的覆盖度、Table 3 的 GO/KEGG 富集，以及 Fig. 2 的物种顺序敏感性分析。