dataesr/scientific-paragraphs-categorization huggingface dataset:
Spectrum-preserving string sets in relation to k-mer indexing One of the fastest and most space-efficient techniques available to index and associate information to k-mers is BLight  (Marchet et al. , 2019b) , a hash table scheme tailored to large sets of k-mers. Given a collection of datasets, the input data given to BLight is a SPSS of the k-mers from the union de Bruijn graph of this collection. In its inner steps, BLight relies on a particular type of SPSS, where in each sequence of the SPSS all k-mers need to have the same minimizer. Definition 7 Minimizer  (Roberts et al. , 2004). The m-minimizer of a sequence S is the smallest substring of size m in S, according to some ordering. Here, m-minimizers are computed on k-mers, hence m < k, and the order on m-mers is given by a hash function (i.
e. not the lexicographic order). Definition 8 BLight indexing scheme  (Marchet et al. , 2019b). Given a set of k-mers X, let S be a SPSS of X such that in each string s 2 S, all kmers in s have the same m-minimizer. Then BLight uses S to compute a static, collision-free hash table where the set of keys is X. In the original BLight article, the SPSS of X is the set of all the super-k-mers found in the unitigs, as defined below. Definition 9 Super-k-mer  (Kokot et al. , 2017). Given a sequence x, a super-k-mer is a substring of x of maximal length such that all k-mers within that substring have the same m-minimizer sequence. Observation 1 Given a set of k-mers X, the set of all super-k-mers constructed from the unitigs of the DBG of X is a SPSS of X. Concretely, the original version of BLight takes as input the unitigs of the DBG of X, and transforms them into another SPSS: the super-k-mers of unitigs, partitioned according to their minimizers.
However, it is important to note that this is not the only possible SPSS scheme that can be used by BLight. In fact, in this article we will use another one. In the inner workings of BLight, querying a k-mer x consists in first computing the minimizer of x to identify in which partition it is expected to be found. Then a minimal perfect hash function  (Limasset et al. , 2017)  associates x to its position within a sequence of the SPSS. The position is then converted into a number that indicates a location in memory that can be used to associate some piece of information to each k-mer. Of note, BLight only records information about the set of k-mers itself, but has no additional information such as their presence/absence within a collection of datasets, nor their counts. Another data structure will be needed along with BLight to record such information, which is in fact the purpose of REINDEER.
So far, we have reviewed the following SPSSs for a set of k-mers X: X itself, the unitigs of X, any set of super-k-mers that together contains all k-mers of X (such as the super-k-mers of the sequencing reads where X originated from), and the super-k-mers of the unitigs of X. To this list we can add the recently introduced (and equivalent) concepts of  UST and simplitigs (B rinda et al. , 2020; Rahman and Medvedev, 2020). They are SPSSs that aim to minimize their total number of nucleotides. Note that contigs resulting from a genome or transcriptome assembly of X, unlike unitigs, are not a SPSS as they typically discard some of the k-mers to generate consensus sequences. Table  1  recapitulates all SPSS schemes (monotigs will be defined later in the article). In the next section, we will show that the choice of SPSS is important for our specific application.
SPSSs for indexing k-mer counts Due to the stochasticity of sequencing coverage, genomes and transcriptomes are not evenly covered by sequencing reads. Thus, kmers coming from regions that have the same copy-number (in genomes,-or abundance, in transcriptomes) often have close but non-identical counts. Yet, if those k-mers had identical counts, such redundancy could be exploited to save space when indexing counts. While it would be unrealistic to assume that k-mer counts are constant across long genomic regions of same copy-numbers (or of same abundances across a transcript), we will assume it for shorter regions (unitigs) throughout the rest of the article. Assumption 1 Within a dataset, the counts of k-mers that are part of the same unitig are assumed to all be identical. We argue that Assumption 1 yields a robust approximation of kmer counts.
Count vectors and SPSSs Using the indexing scheme presented in the previous section (a SPSS indexed by BLight), our aim is to associate to each k-mer its abundances in datasets. Definition 10 Count-vector. Given an ordered list of datasets and a kmer x, the count-vector of x is a vector in which the integer at position i represents the number of times x is seen in the ith dataset. Our initial motivation is to seek a SPSS scheme where a single count-vector can be associated to each string of the SPSS. In other words, for each string s of the sought SPSS, all k-mers in s need to have the same count-vector. Observation 2 Under Assumption 1, given a super-k-mer constructed from the unitigs of a union DBG, it is possible that not all k-mers in the super-k-mer have the same count-vector. We show a proof of Supplementary Observation S2, illustrated by Figure  1.
It is immediate that a possible instance of the sought SPSS is X itself. Since each string of that SPSS only contains a single k-mer, a single count-vector is associated to each element of the SPSS. However this is not a scalable solution, as thousands of mammalian-sized datasets contain billions of distinct k-mers, leading to prohibitively high memory consumption. Yet recall that BLight allows to index any SPSS, as long as it satisfies the minimizer condition of Definition 8. It turns out, perhaps surprisingly, that none of the SPSS schemes of the previous section would be suitable for associating elements to single count-vectors. We describe why below. Most of the time, the k-mers within a unitig do not share the same minimizer, thus unitigs cannot be used as a SPSS for BLight. This is why in the original BLight scheme, super-k-mers are extracted from the unitigs to construct a suitable SPSS.
Even so, a second issue occurs: in the union DBG, two k-mers coming from two different datasets can overlap over k -1 nucleotides, forming in a unitig a ðk þ 1Þ-mer that exists in no single dataset. We will call such unitigs chimeric (see Fig. 1 , and leftmost unitig in Fig. 2 ). It is clear that k-mers within chimeric unitigs do not all have identical count-vectors. This leads to the impossibility of associating a single count-vector to chimeric unitigs or even to super-kmers of chimeric unitigs. Of note, the other SPSS schemes UST and simplitigs aim to merge unitigs as much as possible. These schemes suffer from the same issue of having multiple count-vectors within a single sequence, at an even more extreme level than with single unitigs.
Monotigs As we saw in the previous section, super-k-mers constructed from the unitigs of the union DBG were likely to be a suitable SPSS, except that Observation 2 shows that a single count-vector cannot always be associated to each of them. However, this issue does not arise when considering a single dataset at once. This allows us to introduce the new concept of monotig. Definition 11 Monotig. A monotig is the sequence of a path in the union DBG in which all constituent k-mers have the same count-vector and the same minimizer. Observe that monotigs are not necessarily substrings of super-k-mers of unitigs as they can in principle span multiple unitigs (see e. g. Fig. 3  step 2/). The set of monotigs forms a partition of the nodes of the DBG. Note that contrary to other SPSSs, due to the count vector constraint, monotigs are not solely defined using k-mers of the de Bruijn graph.
REINDEER data structure Given a collection of datasets, REINDEER is an index that associates to any k-mer its counts in all datasets. As a byproduct of recording counts, it is also possible to query the presence/absence of kmers within these datasets. This makes REINDEER a memoryefficient representation of colored de Bruijn graphs, such as other recent methods in the literature  (Muggli et al. , 2017; Pandey et al. , 2018; Yu et al. , 2018) , and in particular Bifrost  (Holley and Melsted, 2019)  which indexes unitigs through the minimizers of their constituent k-mers. But note that REINDEER does more than representing colors (it also records unitig-averaged abundances), and it is static (unlike Bifrost) and not particularly designed for efficient graph traversal. In line with recent works  (Harris and Medvedev, 2018; Pandey et al.
, 2018; Yu et al. , 2018) , REINDEER conceptually transforms an input collection C of datasets into a set of multisets of k-mers. As a pre-requisite, a compacted DBG needs to be built for each dataset [e. g. using BCALM2  (Chikhi et al. , 2016) ]. REINDEER then takes as input the collection of compacted DBGs, and a single count value Compacted unipaths in a de Bruijn graph Super-k-mers of reads Substrings of reads of maximal length such that all k-mers in a super-k-mer share the same m-minimizer [e. g. KMC  (Kokot et al. , 2017)]  Note: unlike all others, this SPSS represents the multiset of k-mers (with duplicates) from the reads, not a set of distinct k-mers Super-k-mers of unitigs Same as above, except substrings of unitigs instead of substrings of reads [e. g. BLight  (Marchet et al. , 2019b) ] UST  (Rahman and Medvedev, 2020)  Set of sequences obtained by greedily concatenating unitigs to minimize the total number of nucleotides in the SPSS Simplitigs  (B rinda et al.
, 2020)  Similar to Rahman and Medvedev (2020) Monotigs A set of paths that covers the (uncompacted) de Bruijn graph such that all k-mers have an identical countvector and minimizer Note: See also Figure  2  for an example of each category. bols). In this first panel, the minimizer of each k-mer is highlighted in grey (k ¼ 4, m ¼ 2). Dots below k-mers symbolize their non-zero abundance (filled symbols) or absence (1) across the three datasets. In the five other panels, sequences within each SPSS scheme are roughly represented according to the positions of constituent k-mers in the DBG, only for visual indication. Observe that monotigs are the only SPSS scheme where each sequence can be associated to a single combination of colored dots Fig. 2. Left: 2 datasets and their k-mers (k ¼ 5). Right: a union DBG is built over these k-mers, and contains 3 unitigs (top row).
Symbols (e. g. circle, star) above each k-mer symbolize the per-dataset abundances. In the left-most unitig, the two k-mers have the same abundance information. Thus the monotig is here equivalent to the unitig. In the center and right-most unitigs, k-mers that have contrasted abundances share a k -1 overlap and can be compacted. On the contrary, monotigs will stop at differences between the coverage profiles of overlapping k-mers per unitig present in each DBG. It represents implicitly the union DBG of all the compacted DBGs, which is never explicitly constructed in memory. To summarize, REINDEER is built in three steps, illustrated in Figure  3 : 1. For each dataset, build an individual DBG that also records kmer counts, averaged per unitig. 2. Construct monotigs (according to the greedy algorithm of Section 5.
Construction of the monotigs We propose a greedy algorithm to compute a set of monotigs efficiently. The algorithm takes as input a set of compacted DBGs (one DBG per dataset). First, super-k-mers of unitigs are computed for each dataset. The rationale for using super-k-mers instead of k-mers is to save space, as opposed to having to store all k-mers on disk. Each super-k-mer records its count in the DBG it originates from (there is a unique count, according to Definition 4). The super-kmers are partitioned into files according to their minimizers. At this step, the same k-mer may be present in multiple super-k-mers within a file (in fact, the k-mer is repeated as many times as the number of datasets where it is present). Then, for each minimizer file, super-k-mers are broken into their constituent k-mers.
The k-mers and their count-vectors are inserted into a hash table (github. com/martinus/robin-hood-hashing). When a k-mer is first inserted, it has a count-vector that records the abundance of its originating super-k-mer in the corresponding dataset. When a duplicate of a k-mer already in the hash table is met by parsing another super-k-mer (i. e. the same k-mer coming from another dataset), the associated count-vector is updated by adding the abundance of the other dataset. In each minimizer file, monotigs are constructed by greedily merging k-mers having identical count-vectors and a ðk À 1Þ overlap. Concretely, each k-mer at an extremity of a monotig queries the hash table for the existence of a (uncompacted) DBG neighbor (e. g. for a right extremity, neighbors are the ðk À 1Þ-suffix of the k-mer appended with either A, C, T or G).
Construction of the count-vector matrix Once all monotigs are computed, they are given as input to BLight. The BLight scheme is slightly modified to associate a single memory location to all k-mers within a monotig, instead of one memory location per k-mer. This is done in a straightforward way by returning the monotig's identifier instead of the position of the queried k-mer within that monotig. Once the BLight index is built, a count-vector matrix M is created such that its rows are the monotigs count-vectors, organized according to the order of the monotigs referenced by the values of the BLight hash table. In other words, the value M½i½j in this matrix gives the count of all k-mers within the ith monotig in the jth dataset. The matrix is stored in a row-major order; each row can be accessed efficiently during queries.
Query Queries in REINDEER are performed as follows. A query sequence S of size L is decomposed into its constituent k-mers, which are then individually queried in the index. Behind the scenes, the index converts each k-mer into a monotig identifier, used to access the corresponding row of the de-duplicated count-vector matrix, then retrieves the counts associated to this k-mer in all datasets. Note that the presence/absence of a query k-mer x can be directly inferred from the count-vector matrix. Indeed, if x has a non-zero count in dataset j, it means that x is present in one of the unitigs of the DBG of dataset j and thus in some monotig i of the union DBG. Thus, the presence of x can be deduced by computing whether M½i½j > 0. To determine the abundance of S in each dataset, we first check whether S is present in the dataset: whether at least h of the constituent k-mers of S have non-zero abundance in the dataset (by default, h ¼ 40%).
If REINDEER is asked to only determine the presence/absence of S, the query stops here. For abundance queries, a matrix of integers Count is recorded, of size m Â c where m ¼ L À k þ 1 is the number of k-mers in S and c the number of datasets. Each value Count½i½j corresponds to the count of the ith k-mer of S inside dataset j. Instead of directly reporting the matrix Count, we perform an additional step that de-duplicates identical values within each column. For example if in a given dataset j all the counts of k-mers present in S are identical (jfCount½i½j; 8is:t:Count½i½j > 0gj ¼ 1), then we report a single count value for this dataset. On the contrary, if not all Count½i½js are identical at a fixed j, then a list containing all seen count values is reported for dataset j. This second case happens when k-mers from S fall into different unitigs of dataset j, and these unitigs have different abundances (as defined by Definition 4).
Thus the final query result for a given sequence S is a tuple containing c (possibly single-valued) lists. Fig. 3. Overview of REINDEER index construction. At step 1/, for each dataset, the (compacted) de Bruijn graph is given as input along with the count of each unitig. At step 2/, monotigs (corresponding to paths in dark grey) are computed on the k-mers of the union de Bruijn graph of all datasets, and these monotigs are indexed. During step 3/each monotig is associated (through an integer array) to a row in the de-duplicated count-vector matrix (rightmost matrix). In this matrix no two rows are equal, and in practice each row is compressed An example of REINDEER output is given in Supplementary Figure  S1. Relying on allows for fast queries and, unlike other methods based on the Burrows-Wheeler transform, a constant (and small) number of memory accesses are performed.
Query complexity for the presence/absence (or abundance) of a sequence of length L ðL > kÞ in an index of c datasets is in time OðL Â cÞ. Although queries that scale linearly with the number of datasets are not ideal theoretically, in practice engineering mitigates this problem. Indeed, grouping all datasets in a single index enhances cachelocality and allows rapid queries by reaching all datasets for a given k-mer in less than c RAM accesses. Other data structures [Mantis  (Pandey et al. , 2018) , Bigsi  (Bradley et al. , 2019) ] also have this query complexity. Moreover, a main focus of REINDEER is to have a low-footprint during queries. This is possible since REINDEER benefits from compression, which allows loading in-memory all datasets information at once while reducing the memory footprint.
Discretization of counts If the accuracy of k-mer counts is not critical, then encoding counts using reduced integer precision leads to more effective deduplication of the count-vector matrix. In REINDEER, we implement two different techniques. (i) Applying a function (termed discretization) that encodes counts from 0 to 50 000 in 8-bit integers, ensuring that discretized counts are at most 5% different from the real raw counts (Following code by G. Rizk, github. com/GATB/ gatb-core/blob/f58d96b/gatb-core/src/gatb/tools/collections/impl/ MapMPHF. hpp#L85). (ii) A log 2 transformation of counts (formally, maxð0; d log 2 ðcountÞeÞ) yields an even more extreme discretization (in terms of loss of precision). An example of these transformations is shown in Table  2. We emphasize that these are not the only possible discretization schemes.
Low-memory de-duplication of rows in the matrix We iteratively compute the count-vectors of monotigs and compress them with run-length encoding (RLE) (github. com/powturbo/ TurboRLE), and then partition the whole multiset of count-vectors, using hashing, into files stored on disk. When a count-vector is written to disk, its monotig identifier given by BLight is also recorded next to it. Then, reading each file separately, we select a single representative of each vector by inserting it into an efficient dynamic hash table  1. Once a partition is processed, we write the set of deduplicated count vectors to disk, and record the mapping between monotig indices and their positions in the de-duplicated count-vector matrix.
Results In their work,  Solomon and Kingsford (2016)  indexed 2652 human RNA-Seq samples to demonstrate the scalability of their approach. Since then, other competing methods have also used this dataset. It was further reduced to 2585 datasets to remove experiments containing short reads that could not be indexed with 21-mers  (Harris and Medvedev, 2018) , and has become a de facto benchmark. We use results from a recent and exhaustive review  (Marchet et al. , 2019a)  to compare REINDEER with the state-of-the-art in indexing collections of datasets. Despite not having run all methods on the same machine, the comparison of space usages for each data structure will nevertheless be accurate; results regarding execution times will certainly be machine-dependent but orders of magnitudes are expected to be roughly preserved.
We compare our approach with five others: Solomon and Kingsford's original Sequence Bloom Tree (SBT)  (Solomon and Kingsford, 2016) ; HowDeSBT, the most recent improvement of SBT  (Harris and Medvedev, 2018) ; other hashing-based methods [BIGSI  (Bradley et al. , 2019) , SeqOthello  (Yu et al. , 2018) ]; and a recent method relying on a de Bruijn graph [Mantis  (Pandey et al. , 2018) ]. Among those approaches, only REINDEER and Mantis support exact k-mer queries, all the others are probabilistic, meaning that a given k-mer may be said to be present, while it is not. REINDEER is the only index that provides count information (as opposed to just presence/absence). We provide scripts and guidelines (github. com/ kamimrcht/REINDEER/tree/master/reproduce_manuscript_results) to reproduce the following results.
Comparison to state of the art We first build REINDEER indexes on the 2585 datasets and filter out the rare k-mers on the same criteria as the other methods (the following thresholds, set according to the dataset sizes, were used: https://www. cs. cmu. edu/$ckingsf/software/bloomtree/srr-list. txt), resulting in a total of $3755 millions of distinct k-mers to index after filtering. We then compare our performance metrics to those reported by other tools on the same dataset  (Marchet et al. , 2019a). Several construction modes are assessed: indexing presence/absence information only (for the sake of comparison only as our contribution consists in providing counts); and indexing counts in different modes (normal, discretized, log 2 ). To be comparable to other results, we used a k value of 21 (and m ¼ 10).
Scalability and influence of k In this paragraph we assess the performance of constructing REINDEER on several datasets sizes and k sizes. To fairly compare the different runs, we selected a set of 2512 datasets that have reads of lengths ! 31 bases among the 2585 previously mentioned datasets. We assessed the scalability of the REINDEER index (for raw counts) on 10 to 2512 datasets (Table  4 ). The required grow roughly linearly with the number of distinct k-mers. The performance of REINDEER can be impacted by the chosen k-mer size. Intuitively, longer k-mers can lead to larger monotigs, thus to a reduction of REINDEER index size. We show the behavior of REINDEER on several k values in Supplementary Table  S1. Monotigs are longer with k ¼ 31 (35 bases on average, compared to 22 bases on average for k ¼ 21).
Comparison with the jellyfish and other hash tables We selected Jellyfish  (Marc¸ais and Kingsford, 2011)  for a comparison with REINDEER because it is one of the most straightforward existing alternatives: Jellyfish implements a hash table that associates to each k-mer its count within a dataset. We compare REINDEER and Jellyfish by estimating the space consumption of Jellyfish per key to index, and let aside the abundance storage. The space usage of recording 4 billion distinct k-mers with Jellyfish is approximately 2 l Â 2kÀlþrþ1 8 ¼ 92 GB (according to Jellyfish manual, with l ¼ log 2 ðK=0:8Þ; r ¼ b log 2 ð62Þc À 1, k ¼ 21 and K ¼ 4 Á 10 9 ). In comparison, REINDEER indexed monotigs and their associations to memory locations using roughly 15 GB of memory, that is, a 84% space saving relative to Jellyfish.
We also briefly compare the monotigs indexing part of REINDEER with two other hashing schemes: Short Read Connector (SRC)  (Marchet et al. , 2020)  and the original BLight scheme  (Marchet et al. , 2019b). SRC indexes k-mers directly, was shown to outperform classical hashing techniques (such as Cþþ unordered maps). As described above, BLight indexes super-k-mers of unitigs. We experimentally tested the original BLight implementation on 4 billion distinct k-mers, resulting in 15 GB of memory usage, similarly to REINDEER. This demonstrates that switching the SPSS strategy from unitig super-k-mers to monotigs has no negative impact on the index size. On the other hand, SRC used 23 GB of memory.