Fulgor: A fast and compact k-mer index for large-scale matching and color queries.
Fulgor: A fast and compact k-mer index for large-scale matching and color queries.
复制标题
Fulgor：一种快速、紧凑的 k-mer 索引，用于大规模匹配和颜色查询。
DOI：
10.1101/2023.05.09.539895
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Patro,Rob
中科院分区：
文献类型：
--
作者：
Fan,Jason;Singh,NoorPratap;Khan,Jamshed;Pibiri,GiulioErmanno;Patro,Rob
序列识别或匹配的问题--从给定的集合中确定可能包含短的、查询的核苷酸序列的参考序列的子集--与计算生物学中的许多重要任务相关，例如元基因组学和泛基因组分析。由于这类分析的复杂性和参考资料收集的规模庞大，对这一问题采取资源效益高的解决办法至关重要。这带来了用数据结构表示引用集合的三重挑战，该数据结构查询效率高，内存使用少，并且可以很好地扩展到大型集合。为了解决这个问题，我们描述了一种高效的有色De Bruijngraph索引，它是由AK-mer字典和压缩倒排索引相结合而产生的。所提出的索引充分利用了着色紧致de Bruijn图中的单元群是单色的这一事实(即，单元群中的allk-mers具有相同的起源或颜色参考集合)。具体地说，单元组以颜色顺序保存在词典中，从而允许以每个单元组最少1+O(1)比特对从k-MERS到其颜色的映射进行编码。因此，在几乎没有空间/时间开销的情况下，每个单位一种颜色存储在索引中。通过将这一特性与用于整数列表的简单但有效的压缩方法相结合，该索引实现了非常小的空间。我们在一个名为Fulgor的工具中实现了这些方法，并进行了广泛的实验分析，以证明我们的工具比以前的解决方案有所改进。例如，与Themisto相比--在索引空间和查询时间方面是最强大的竞争对手--Fulgor需要的空间要少得多(对于150,000个沙门氏菌肠菌体集合，空间最多减少43%)，颜色查询的速度至少是Themisto的两倍，构建速度快2-6倍。
The problem of sequence identification or matching—determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence—is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficientcolored de Bruijngraph index, arising as the combination of ak-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph aremonochromatic(i.e., allk-mers in a unitig have the same set of references of origin, orcolor). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map fromk-mers to their colors in as little as 1 +o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto—the strongest competitor in terms of index space vs. query time trade-off—Fulgor requires significantly less space (up to 43% less space for a collection of 150,000Salmonella entericagenomes), is at least twice as fast for color queries, and is 2–6faster to construct.