基于小波树(Wavelet Tree)的泛基因组索引方法Panaln：高效序列比对与变异检测的新策略

本研究针对泛基因组(pangenome)索引构建空间大、检索效率低的难题，开发了基于小波树的索引工具Panaln。通过线性模型整合参考基因组与变异数据(VCF)，提出批量计算策略加速计数查询(Occφ)，并创新性地采用最长相等重叠片段(LEOF)作为动态种子，结合改进的波前算法(WFA)实现高精度序列比对。实验表明，Panaln在人类基因组数据中索引空间较BWBBLE减少69%，比对准确率达95.6%，为复杂变异(SNP/INDEL)分析提供了轻量化解决方案。

　　

随着测序技术的快速发展，生命科学已进入"泛基因组时代"。传统单参考基因组方法存在参考偏差问题，而现有泛基因组索引工具如GCSA和VG面临指数级构建复杂度、内存消耗大等挑战。尤其当处理包含数十万单核苷酸多态性(SNP)和插入缺失(INDEL)的群体变异数据时，Burrows-Wheeler变换(BWT)类方法需要处理爆炸式增长的路径空间，而k-mer哈希方法则难以有效捕捉小变异。这促使研究者探索更高效的索引结构，在保证变异敏感性的同时提升计算效率。

西安电子科技大学Lilu Guo等人在《Bioinformatics》发表的研究，开发了基于小波树的泛基因组索引系统Panaln。该方法创新性地采用线性模型整合参考基因组与变异数据(VCF)，通过IUPAC编码(国际纯粹与应用化学联合会标准)将SNP转换为16种扩展字符，并将INDEL片段与侧翼序列串联存储。关键技术包括：1)构建混合小波树索引，对单态碱基(Σ_uniq)采用平衡小波树，对多态符号(Σ_poly)采用霍夫曼编码树；2)开发批量Occ_φ查询算法，通过共享节点rank运算提升计数效率；3)基于D数组(差异位置数组)设计LEOF种子策略，结合改进的波前算法实现包容性比对。

3.1 泛基因组索引

研究采用Huang等提出的线性表示模型，将dbSNP数据库的变异映射至参考基因组。如图2所示，SNP通过IUPAC编码嵌入主链（如"W"表示A/T多态），INDEL则与长度-k上下文拼接后追加存储。索引核心是改进的FM-Index结构：BWT字符串通过位向量U分离单态/多态符号，分别构建平衡树（高度固定为2）和霍夫曼树（平均高度1.8），如图3所示。该设计使Occ查询缓存命中率提升3倍，索引体积较传统固定长度编码减少41%。

3.2 泛基因组比对

提出的LEOF种子策略（定义1）通过合并正反链D数组的不连续点定位差异区域。如图4所示，在含3个测序错误的101bp读段中，LEOF能准确识别46bp无变异片段。比对阶段采用两步优化：1)通过小波树的locate查询定位种子；2)用改进的WFA进行延伸，其扩展函数支持IUPAC编码的模糊匹配（如"W"可匹配A/T）。

实验结果显示，在17×覆盖度的人类Illumina数据中，Panaln达到99.95%比对率，SNP检测F值较HISAT2提高12.5%。在构建效率方面，全基因组索引仅需94分钟和114GB内存，较HISAT2节省83%时间。值得注意的是，在PacBio-CCS长读长数据中，其98.94%的比对率显著优于BWBBLE（无法运行）和Giraffe（38.5%）。

该研究突破了传统泛基因组索引的空间效率瓶颈，其混合小波树结构为处理大规模变异数据集提供了新思路。相较于基于图的索引方法，线性模型在保持变异信息完整性的同时，更易于整合到现有分析流程中。LEOF种子的动态特性有效缓解了"延迟现象"，而改进的WFA算法首次实现了对IUPAC编码的直接比对。这些创新使得Panaln特别适合群体基因组研究和临床变异检测，为精准医学时代的序列分析提供了高效工具。未来工作可进一步优化长读长比对策略，并探索在结构变异(SV)检测中的应用潜力。