序列识别或匹配的问题-从给定集合中确定可能包含短,查询的核苷酸序列-与计算生物学中的许多重要任务有关,如宏基因组学和pangenome分析。由于此类分析的复杂性和参考集合的大规模,因此解决此问题的资源高效解决方案至关重要。这提出了用高效查询的数据结构表示引用集合的三重挑战,内存使用率很低,并扩展到大型收藏品。为了解决这个问题,我们描述了一个有效的彩色deBruijn图索引,作为k-mer字典与压缩的倒排索引的组合而产生。建议的索引充分利用了以下事实:彩色压缩的deBruijn图中的单位是单色的(即,一个Unitig中的所有k-mer都有相同的起源参考集,或颜色)。具体来说,系统按颜色顺序保存在字典中,从而允许以少至每单位1+o(1)位编码从k-mer到它们的颜色的映射。因此,每个Unitig一个颜色存储在索引中,几乎没有空间/时间开销。通过将此属性与整数列表的简单但有效的压缩方法相结合,该指数获得的空间非常小。我们在名为Fulgor的工具中实现这些方法,并进行广泛的实验分析,以证明我们的工具比以前的解决方案有所改进。例如,与Themisto相比-在指数空间方面最强的竞争对手查询时间权衡-Fulgor需要更少的空间(对于150,000个沙门氏菌基因组的集合,空间减少多达43%),至少是颜色查询的两倍,并且是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 efficient colored de Bruijn graph index, arising as the combination of a k-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 are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-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,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6[Formula: see text] faster to construct.