BWT 与 FM-index：从 bzip2 到基因组比对
内容提要
Burrows-Wheeler 变换（BWT）是一种通过对字符串进行循环旋转并按字典序排序生成的新序列，具有可逆性，能够仅凭最后一列恢复原始字符串。FM-index 是基于 BWT 的全文索引结构，支持在压缩空间内进行精确模式匹配。BWT 广泛应用于数据压缩（如 bzip2）和基因组比对（如 BWA），推动了二代测序技术的发展。
关键要点
-
Burrows-Wheeler 变换（BWT）通过对字符串进行循环旋转并按字典序排序生成新序列，具有可逆性。
-
FM-index 是基于 BWT 的全文索引结构，支持在压缩空间内进行精确模式匹配。
-
BWT 广泛应用于数据压缩（如 bzip2）和基因组比对（如 BWA），推动了二代测序技术的发展。
-
BWT 的可逆性证明依赖于 LF-mapping 性质，仅凭最后一列 L 就可以恢复原始字符串 T。
-
BWT 在压缩领域的核心价值在于其聚簇效应，使得相同字符倾向于连续出现。
-
FM-index 的 backward search 算法实现了 O(m) 的精确匹配，时间复杂度与文本长度无关。
-
BWA-MEM 是基于 FM-index 的短读段比对工具，适用于二代测序数据的处理。
-
在实际应用中，BWT 和 FM-index 的设计哲学强调了空间与时间的权衡，适应了大数据处理的需求。
延伸问答
什么是 Burrows-Wheeler 变换（BWT）？
BWT 是一种通过对字符串进行循环旋转并按字典序排序生成的新序列，具有可逆性，能够仅凭最后一列恢复原始字符串。
FM-index 是什么，它的主要功能是什么？
FM-index 是基于 BWT 的全文索引结构，支持在压缩空间内进行精确模式匹配。
BWT 如何在数据压缩中发挥作用？
BWT 通过聚簇效应使得相同字符倾向于连续出现，从而提高压缩效率，常用于 bzip2 等压缩工具。
BWA-MEM 是如何利用 FM-index 进行基因组比对的？
BWA-MEM 使用 FM-index 的 backward search 在参考基因组的 BWT 上寻找超级最大精确匹配（SMEM），并进行种子延伸。
BWT 的可逆性是如何证明的？
BWT 的可逆性依赖于 LF-mapping 性质，仅凭最后一列 L 就可以恢复原始字符串 T。
FM-index 的 backward search 算法有什么特点？
FM-index 的 backward search 算法实现了 O(m) 的精确匹配，时间复杂度与文本长度无关。
