BIKE：一种具有字母表无关内存和确定性并行性的二进制 K-mer 精确计数器

《IEEE Transactions on Computational Biology and Bioinformatics》：BIKE: A Binary K -mer Exact Counter with Alphabet-Independent Memory and Deterministic Parallelism

　　

摘要：

K-mer计数是生物信息学中的基础性计算任务，支撑着基因组组装、宏基因组分类、错误纠正和相似性分析等工作。现有的精确计数方法依赖于哈希表或静态分配策略，其内存需求随字母表大小和子串长度呈指数级增长，使得这些方法在处理中等到大尺度k值的氨基酸序列时变得不切实际。我们提出了BIKE（Binary K-mer Exact Counter，二值K-mer精确计数器），一种新型精确k-mer计数算法，其内存占用仅取决于输入序列长度n，而与字母表大小k或k-mer长度k无关。BIKE将计数问题分解为n?1个相互独立的基于枢轴的比较块，这些块完全在二值矩阵上操作，每个条目仅需一个比特，并采用并查集聚合机制，保证了对任意多重性的k-mer的精确计数。这种结构上的规律性产生了完全确定的并行度，使得能够建立闭式解析模型，在理想并行执行假设下提供准确的执行时间预测。在真实生物序列上的实验结果证实了功能正确性，并表明与经典精确方法相比，在氨基酸字母表上内存减少了高达三个数量级。基于闭式并行模型的解析性能预测表明，BIKE的FPGA实现有望在中等序列长度上超越基于CPU的动态分配；然而，这些仍为理论估计，有待硬件实现验证。因此，BIKE作为一项理论和数据结构贡献被提出，为字母表无关、精确计数且可确定性并行的k-mer分析建立了新的算法基础。