快速固定参数可解算法计算有根一致森林

### 快速固定参数可解算法计算有根一致森林 在生物信息学中，计算系统发育树之间的距离是一个重要的问题。本文将介绍用于计算两个系统发育树的最大一致森林（MAF）和最大无环一致森林（MAAF）的改进固定参数可解（FPT）算法，并对这些算法进行实验评估。 #### 基本概念 - **最大一致森林（MAF）**：对于两个森林 $F_1$ 和 $F_2$，MAF 是具有最少组件数量的一致森林。我们用 $m(F_1, F_2)$ 表示 $F_1$ 和 $F_2$ 的 MAF 中的组件数量，用 $e(F_1, F_2, F)$ 表示最小边集 $E$ 的大小，使得 $F \div E$ 是 $F_1$ 和 $F_2$ 的一致森林，其中 $F$ 是 $F_2$ 的一个森林。Bordewich 和 Semple 证明了 $d_{spr}(T_1, T_2) = e(T_1, T_2, T_2) = m(T_1, T_2) - 1$。 - **最大无环一致森林（MAAF）**：MAAF 是 MAF 的一种特殊情况，它要求一致森林中没有环。我们用 $\tilde{m}(F_1, F_2)$ 表示 $F_1$ 和 $F_2$ 的 MAAF 的大小，用 $\tilde{e}(F_1, F_2, F)$ 表示为了得到 $F_1$ 和 $F_2$ 的 MAAF 而必须在 $F_2$ 的森林 $F$ 中切割的边的数量。Baroni 等人证明了 $hyb(T_1, T_2) = \tilde{e}(T_1, T_2, T_2) = \tilde{m}(T_1, T_2) - 1$。 #### MAF 算法 MAF 算法是一个递归算法，每次调用接受两个森林 $F_1$ 和 $F_2$ 以及一个参数 $k$，并决定是否 $e(T_1, T_2, F_2) \leq k$。具体步骤如下： 1. **失败情况**：如果 $k < 0$，则不存在最多 $k$ 条边的子集 $E$ 使得 $F_2 - E$ 是 $T_1$ 和 $T_2$ 的一致森林，返回 “no”。 2. **成功情况**：如果 $|R_t| \leq 2$，则 $\dot{F}_2 \subseteq \dot{T}_1$，因此 $\dot{F}_2 \cup F$ 是 $F_1$ 和 $F_2$ 的一致森林，返回 “yes”。 3. **修剪最大一致子树**：如果 $R_t$ 中没有节点 $r$ 是 $\dot{F}_2$ 的根，则转到步骤 4。否则，将 $r$ 从 $R_t$ 中移除并添加到 $R_d$ 中，将 $\dot{F}_2$ 中对应的子树移动到 $F$ 中。切割 $\dot{T}_1$ 中的边 $e_r$ 并进行强制收缩以移除 $r$ 的父节点。这不会改变 $F_2$，因此也不会改变 $e(T_1, T_2, F_2)$。返回步骤 2。 4. 选择 $\dot{T}_1$ 中的一个兄弟对 $(a, c)$，使得 $a, c \in R_t$。 5. **生长一致子树**：如果 $(a, c)$ 不是 $\dot{F}_2$ 的兄弟对，则转到步骤 6。否则，将 $a$ 和 $c$ 从 $R_t$ 中移除，在两棵树中标记它们的父节点为 $(a, c)$，并将其添加到 $R_t$ 中。返回步骤 2。 6. **切割边**：区分三种情况： - **情况 6.1**：如果 $a \not\sim_{F_2} c$，则进行两个递归调用 $Maf(F_1, F_2 \div \{e_a\}, k - 1)$ 和 $Maf(F_1, F_2 \div \{e_c\}, k - 1)$。 - **情况 6.2**：如果 $a \sim_{F_2} c$ 且从 $a$ 到 $c$ 在 $\dot{F}_2$ 中的路径有一个悬挂节点 $b$，则进行一个递归调用 $Maf(F_1, F_2 \div \{e_b\}, k - 1)$。 - **情况 6.3**：如果 $a \sim_{F_2} c$ 且从 $a$ 到 $c$ 在 $\dot{F}_2$ 中的路径有 $q \geq 2$ 个悬挂节点 $b_1, b_2, \ldots, b_q$，则进行三个调用 $Maf(F_1, F_2 \div \{e_{b_1}, e_{b_2}, \ldots, e_{b_q}\}, k - q)$、$Maf(F_1, F_2 \div \{e_a\}, k - 1)$ 和 $Maf(F_1, F_2 \div \{e_c\}, k - 1)$。 下面是 MAF 算法的流程图： ```mermaid graph TD; A[开始] --> B{k < 0?}; B -- 是 --> C[返回 "no"]; B -- 否 --> D{|R ```