生信算法（1）——BWT算法

一、引言：BWT 是什么？

BWT（Burrows–Wheeler Transform）是一种字符串变换技术，最初用于数据压缩领域。它将字符串中的相似字符聚集在一起，便于后续压缩。随着高通量测序的发展，BWT 被广泛应用于基因组序列比对工具中（如 BWA、Bowtie）用于构建索引，加速短序列（reads）在参考基因组中的定位。

二、BWT 的构建过程

步骤概览：

1. 向原始字符串末尾添加一个特殊符号 $（表示终止，且在字典序中最小）；
2. 生成该字符串的所有循环后缀（轮转）；
3. 按字典序对所有循环后缀排序；
4. 取排序后每行的最后一个字符，组成 BWT 序列。

举例说明：

以字符串 ababc 为例：

最终得到的L列为输出：c$baab

三、LF-Mapping：从后往前还原序列

LF-Mapping（Last-to-First Mapping）用于在 BWT 索引中进行“反向遍历”，即从 BWT 序列恢复原始序列。

关键点：

• 排序后的矩阵第一列称为 F 列，最后一列（即 BWT）称为 L 列；
• L 列中某个字符 c 的第 i 次出现，在 F 列中也对应字符 c 的第 i 次出现；
• 这个映射可以用来反向还原原始字符串。

四、FM-Index 构建

FM-Index 是基于 BWT 的压缩全文索引，它使得我们可以在压缩状态下对字符串进行快速搜索。

包含两个辅助结构：

1. C[c]：是所有小于字符 c 的字符在 BWT 的排序前（F 列）中出现的总次数；
2. Occ(c, i)：是字符 c 在 L[1…i] 中出现的次数（包括位置 i）；
3. L[i]：是 BWT 的第 i 位字符（即“最后一列”中位置 i 的字符）；

LF 映射公式：LF(i) = C[L[i]] + Occ(L[i], i)

LF 函数使得我们可以在 BWT 中进行精确模式匹配。

五、Backward Search 算法

在 BWT 和 FM-Index 的支持下，我们可以实现一种从右向左进行的字符串搜索方式，称为 Backward Search。

目标：

在原始字符串中查找模式串 P 是否出现，以及出现的位置。

算法步骤：

1. 初始化 [l, r] 为整个 BWT 序列范围 [1, n]；
2. 从 P 的最后一个字符开始向前处理；
3. 每次更新 l 和 r：l = C[c] + Occ(c, l - 1) + 1 r = C[c] + Occ(c, r)
4. 若在某次更新中出现 l > r，说明模式串不匹配；
5. 最终 [l, r] 区间内的行对应原文中所有匹配的位置。

示例：匹配 “ana” in BWT(“banana”)

原文为 banana$，BWT 为 annb$aa。

搜索过程：

• i=3, 字符 = ‘a’ ⇒ 更新 l, r；
• i=2, 字符 = ‘n’ ⇒ 更新 l, r；
• i=1, 字符 = ‘a’ ⇒ 更新 l, r。

若最终 l ≤ r，则表明“ana”在原文中有匹配。

六、BWT 的优势与应用场景

优势 ✅：

• 压缩效果好：BWT 后字符更趋集中，适用于压缩算法如 RLE、MTF 等；
• 支持快速匹配：结合 FM-Index，模式串搜索时间复杂度为 O(m)，与原文长度无关；
• 节省空间：相较于后缀数组或后缀树，占用内存更小。

局限 ❌：

• 构建索引需要完整读取原文，初始成本高；
• 本质上只支持精确匹配，模糊匹配需扩展实现。

七、在基因组比对中的应用

BWT + FM-Index 是现代高通量测序比对工具的核心组件之一：

• BWA：使用 BWT 构建参考基因组索引，通过 FM-Index 实现快速 read 匹配；
• Bowtie/Bowtie2：相似原理，优化了短序列匹配速度和内存占用；
• SOAP2、STAR 等工具也采用了类似思想进行加速。

这些工具普遍采用 “种子+扩展” 策略：先用 BWT 匹配种子，再用 Smith-Waterman 等算法延伸比对区域。

八、总结与回顾