颜林林
(2022-07-28 08:50):
#paper doi:10.1093/bioinformatics/btac137 Bioinformatics, 2022, BWA-MEME: BWA-MEM emulated with a machine learning approach. 看到李恒在Twitter上转发这篇文章，本以为大神又升级了bwa mem2，之后发现原来是他人的作品，得到了李恒钦点而已。作为某个知名软件的后继者，必然是要在某个方面有较大改进的，这篇的改进主要在性能。用于高通量测序数据的短序列比对算法，通常都是先用精确匹配种子（这几乎都是查表法在常数时间内完成），然后进行延伸匹配。而种子序列的长度选择，是一项比较有技巧性的事，太短可能导致重复匹配（hit）过多，太长则可能大量单词无匹配（在基因组上无该序列）却占据字典，导致字典过大。为此，过去也有一些算法，会采用变长种子来解决该问题（我也设想过这个策略，但惭愧的是，最终未能付诸实践）。而变长种子的策略，存在内存块大小不定、访问频繁等问题，会导致性能瓶颈。在本文中，通过机器学习的方法，在建立种子索引的阶段进行预处理，使得索引能够根据基因组序列数据进行适应，使不同长度种子的内存访问次数固定，从而获得性能提升。在最终的评测中，bwa-meme 能保持与 bwa-mem2 的输出相同，运行速度则提升了 3.45 倍。这篇文章的算法，可以再仔细深入学习下。
BWA-MEME: BWA-MEM emulated with a machine learning approach
翻译
Abstract:
MOTIVATION: The growing use of next-generation sequencing and enlarged sequencing throughput require efficient short-read alignment, where seeding is one of the major performance bottlenecks. The key challenge in the seeding phase is searching for exact matches of substrings of short reads in the reference DNA sequence. Existing algorithms, however, present limitations in performance due to their frequent memory accesses.RESULTS: This article presents BWA-MEME, the first full-fledged short read alignment software that leverages learned indices for solving the exact match search problem for efficient seeding. BWA-MEME is a practical and efficient seeding algorithm based on a suffix array search algorithm that solves the challenges in utilizing learned indices for SMEM search which is extensively used in the seeding phase. Our evaluation shows that BWA-MEME achieves up to 3.45× speedup in seeding throughput over BWA-MEM2 by reducing the number of instructions by 4.60×, memory accesses by 8.77× and LLC misses by 2.21×, while ensuring the identical SAM output to BWA-MEM2.AVAILABILITY AND IMPLEMENTATION: The source code and test scripts are available for academic use at https://github.com/kaist-ina/BWA-MEME/.SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
翻译