ms2 用 move structures 在压缩空间计算泛基因组匹配统计与 SMEM,较 ropebwt3 提速 15 至 34 倍
Fast Pangenome Matching Statistics in Compressed Space with Move Structures

预印本 ms2 用 move structures 在压缩空间计算匹配统计与 SMEM,在人类 22 号染色体的 100 个单倍型上比 PHONI 在线方法快 35 至 48 倍,索引大小相近。
原文摘要
出版方登记 · CrossrefMatching statistics and supermaximal exact matches (SMEMs) are key inputs for sequence homology search and classification. Methods such as MONI, PHONI, and ropebwt3 compute these statistics using compressed pangenome indexes, but are substantially slower than methods that compute approximations of matching statistics, such as pseudo-matching lengths (PMLs). PMLs can be computed quickly in a single pass, but SMEM computation can require overlapping forward or backward passes over the query. We present ms2, a suite of algorithms that use "move structures" to compute matching statistics and SMEMs efficiently in compressed space. Our four algorithms compose move structures for the LF, Ψ, φ, and φ -1 permutations with additional longest common prefix (LCP) array summaries and samples. The algorithms offer different tradeoffs among speed, index size, and support for reporting SMEM offsets. They inherit the move structure's fast, constant-time operations and achieve high throughput by leveraging the move structure's locality of reference. Thanks to recent advances, move structures can be constructed in optimal time and compressed space, including the LCP information needed for "match recovery" during SMEM computation. On 100 haplotypes of human chromosome 22, ms2's fastest algorithm computes matching statistics 35 to 48 times as fast as PHONI's online approach, while using an index of similar size. On the 472-haplotype HPRC2 pangenome and human reads, three ms2 modes achieve speedups of at least 22, 19, and 15 times over ropebwt3, whose index is about 15% the size of ms2's fastest mode. When additionally reporting SMEMs and their offsets, ms2 achieves speedups of 25 to 34 times over ropebwt3. Together, these advances enable online computation of matching statistics and SMEMs at a throughput that supports real-time processing of approximately 21 PromethION nanopore flow cells on a single thread. The ms2 software is open source and available at https://github.com/langmead-lab/ms2. It builds on the open-source TeraTools suite (https://github.com/ucfcbb/TeraTools) and Orbit library (https://github.com/drnatebrown/orbit). Experimental scripts and other details are described in: https://github.com/langmead-lab/ms2-experiments.
页面未能读取全文,以上为出版方登记的摘要;方法与图表见原文
在 472 单倍型泛基因组上匹配统计相对 ropebwt3 提速 15 倍以上,可用于评估是否替换现有压缩索引流程。
来源:bioRxiv 生物信息学 · biorxiv.org