离散数学的降维压缩：李恒与基于 BWT 的 BWA 基因组比对算法

高通量二代测序仪 Illumina 启动一次运行，下机数据往往是几亿到几十亿条仅有一百多个碱基的短序列（reads）。如何在一台普通配置的服务器甚至笔记本电脑上，把这上亿条碎片以几秒几分钟的速度快速找准在三十亿碱基人类参考基因组上的唯一座标？

在 2008 年以前，早期的哈希表索引比对算法（如 MAQ、BLAT）需要几十甚至上百 GB 内存，普通生信实验室的服务器跑着跑着就直接内存溢出（OOM）死机崩盘。2009 年 5 月 18 日，英国桑格研究所的华人计算机学者李恒（Heng Li）与理查德·杜宾（Richard Durbin）在《Bioinformatics》发表了名震寰宇的 BWA 算法（Burrows-Wheeler Aligner）！

他们降维借用了计算机文本无损压缩中的 BWT 变换 与 FM-index 索引数据结构：在基因组末尾加一个终止符，将所有循环移位字符串做字典序排序，保留最后一列。借由不可思议的 LF-mapping（后前行映射关系），整个庞大无比的 3GB 人类基因组被暴力压缩成了常驻内存仅需 1.5 GB 到 2 GB 的极小索引，而且搜寻单个碱基的时间复杂度为常数级 $O(1)$！

这项离散数学的降维打击，直接搬掉了 NGS 规模化普及路上最大的一座算力大山。