dataesr/scientific-paragraphs-categorization huggingface dataset:
For example, consider the problem of finding a RNA transcript within a collection of RNA-seq datasets. Similarly, we can ask to find which datasets contain a specific DNA sequence, such as a gene or a non-coding element, in a collection of bacterial strain genomes. Given the size of many collections and datasets, several different paradigms for storing them in a manner that they can be efficiently queried have been developed -many of which continue to be extended and explored. One paradigm is to store and index datasets as sets of k-length substrings, which are referred to as k-mers. We will refer to collections of datasets as sets of k-mer sets. The methods that use this paradigm first build an index of all k-mer sets, and support the basic query described above by splitting the query sequence into k-mers and determining their presence or absence in the index.
g. , whole transcript or entire gene) but instead provides an approximation. One can view k-mer-based indexes as building blocks for the topic of the present survey: the storage of k-mers coming from multiple datasets, i. e. , sets of k-mer sets. A key aspect of storing sets of k-mer sets comes from the observation that sequencing experiments that are collectively analyzed typically share a large fraction of k-mers. Therefore, significant space savings can be achieved by the identification and clever storage of this redundant information. Here, we focus on the methods underlying the different building blocks (Figure  1 ) of sets of k-mer sets structures. We review the different properties, the types of queries, and the computational performance which they offer. We highlight similarities of methods based on commonalities between building blocks where it is appropriate.
Section 2: Biological applications Several biological and biomedical questions can be addressed by querying sequence databases. Transcriptomics was one of the first specific applications to be described. Solomon + Fig. 1. Overview of set of k-mer sets building blocks. We classified strategies in color-aggregative approaches, and k-mer aggregative approaches. The top row of the figure indicates the general categories of components: a k-mer set, possibly combined with a de Bruijn graph representation; a way to combine multiple sets together; optional compression. Each next row describes a general strategy adopted by one or more methods. and Kingsford gathered more than 2,000 samples of human RNA-seq, consisting of blood, brain, and breast tissue samples from SRA  (8). Since its introduction, this database kept growing, roughly doubling each year.
They confirmed some fusions and reported some novel ones. Fusion transcripts provide interesting targets for cancer immunotherapies since they are susceptible to exhibit tumor-specific markers. Several papers demonstrate how sets of k-mer sets could help mine and analyze collections of microbial samples or genomes, whether they be strains of the same genera (e. g. ,  16 ,000 strain of Salmonella), microbiomes (e. g. , 286,997 genomes from the human microbiome), or more extensive microbial data (e. g. , 469,654 bacterial, viral and parasitic datasets from the ENA). For example, GenomeTrakr (4) was developed to coordinate international efforts in sequencing whole genomes of food-borne pathogens. Indexing and querying this and other databases could lead to improved surveillance of pathogenic bacteria, and thus, elucidate the effectiveness of interventions that attempt to control them.
Section 3: Building blocks We view the storage of a set of k-mer sets as having various (optional) components, which we refer to as building blocks. See Figure  1  for an illustration of this view. In light of this, we cover the basic terminology and concepts that will be used throughout this survey in this section. 3. 1 k-mer set data structures. As previously described, the main building blocks used in sets of k-mer sets representations are, unsurprisingly, schemes to represent k-mer sets. The methods surveyed in this work represent k-mers from sequencing datasets as sets, i. e. k-mers are de-duplicated and unordered. It will be enough to consider the data structures presented in this section as black-boxes that support all or a subset of the following operations: • membership, i. e. , testing whether an element is in the set; • insertion and/or deletion of an element.
Set representations that support insertion and/or deletion are sometimes said to be dynamic, as opposed to static. However, methods to represent k-mer sets are not all equivalent in terms of features and performance. We briefly review their main characteristics in the rest of this section but refer the reader to the recent survey by Chikhi et al. (17)  for further details. Most methods rely on bit vectors to store the presence or absence of k-mers in datasets. A bit vector is an array of bits, e. g. , 00101 represents a bit vector of length 5. A 0 is used to indicate that the k-mer is absent, and a 1 indicates that it is present. A bit vector could be used to record the datasets in which a given k-mer appears, or, alternatively, all the kmers that are contained in a given dataset. However, with a growing number of datasets and k-mers, using plain binary vectors is generally too simplistic, and often compression or other tricks are also incorporated.
Compression. To further optimize space usage, different compression techniques have been applied to sets of kmer sets. Bloom filters and bit vectors are typically objects which are amenable to a number of compression techniques because they are represented in bits. Such objects can be sparse (i. e. when most of the bits are zero, such as when many k-mers belong to only a few datasets from the whole collection) and/or dense (i. e. when most of the bits are 1, such as when many k-mers are present in the same set of datasets). Compression methods exploit these properties. Different compression strategies are shown in Box 2. Bit vector compression. Bit vectors can be efficiently stored using bit-encoding techniques that exploit their sparseness or redundancy. The most prevalent of the methods in this survey are RRR  (29)  or Elias-Fano (EF) (30-32) (see Box 2 (1)).
The principle behind these is to find run of 0's and to encode them in a more efficient manner, reducing the size of the original vectors. Other techniques such as Roaring bitmaps  (33)  adjust different strategies to sub-parts of the vectors. Wavelet trees  (34)  generalized compression of vectors on larger alphabets (i. e. , not just 0's and 1's but e. g. a's, b's, c's, etc). More advanced techniques deriving from the same concept were also proposed specifically for sets of kmer sets  (35). Delta-based encoding. When two sets share many elements, it may be more advantageous to store only the differ-ences between those datasets. For instance, rather than storing two (possibly compressed) bit vectors, one can only store the first bit vector explicitly along with a list of positions of differences for the second.
Section 4: Aggregation techniques As we illustrate in Figure  1  , some methods first index each dataset separately, and then build structures that allow retrieving the name of datasets in which a k-mer is present; whereas others start by representing the set of all k-mers from all datasets, and then attribute them to their datasets of origin (colors). We refer to the former as k-mer aggregative methods and the latter as color-aggregative methods. We will discuss both aggregation methods. We present the few methods that escape this categorization separately.
4. 1 Color-aggregative methods. These methods start by indexing all k-mers across all datasets, and then group together (aggregate) datasets into what will be referred to as color sets. A practical advantage of color-aggregative methods is that a k-mer that appears in many samples will appear only once in the k-mer set. This greatly reduces redundancy in the representation. In this subsection, we give a brief background and history of the methods that fall into this category.
Representation of colors. A color of a given k-mer is frequently used in the literature to identify a dataset containing the k-mer, assuming each dataset is given a unique color. A k-mer may often be contained in multiple datasets and therefore, it is convenient to store the colors of a k-mer using a bit vector. Here, given order of the datasets, a 1 at position i in the bit vector indicates the presence of the k-mer in the i-th dataset, and 0 its absence. A color set is the set of colors associated to a k-mer. Given n k-mers and c datasets, the color matrix is a n × c matrix of bits which describe the presence or absence of each k-mer (in the rows) in each dataset (in the columns). For an example, see Box 1.
Background and method intuition. Iqbal et al. (20)  defined the colored de Bruijn graph (cDBG) -which, moreover, is also the first color-aggregative method. Given a set of input datasets, each dataset is assigned a unique color, so that there are as many colors as datasets. When considering the union of all k-mers across all datasets, it is straightforward to think of using an associative structure to map k-mers to colors. cDBG are DBGs of the set of all pooled k-mers from all the samples (union graph), with each vertex labelled with the k-mer's color set. Colored DBGs allow traversing operations to find paths that contain undirected cycles (bubbles), and finding the individuals in the population that contain a shared or divergent path in each bubble. Cortex implemented those properties, and its bubble-finding algorithm was one of the primary use cases of the cDBG, to detect biological genetic variation in a population without the use of a reference genome.
Space-efficient color-aggregative methods. The first methods that improved upon the memory-and time-efficiency of Cortex were Bloom filter trie (BFT)  (36)  and Vari  (24). These methods achieved a significant reduction in representation size via different strategies. After the introduction of these methods, subsequent improvements were made with the development of Rainbowfish  (37) , Multi BRWT  (35) , Mantis  (38) , SeqOthello  (11) , Mantis+MST  (23) , and Vari-Merge  (16). Most of these recent techniques rely on a more careful encoding of the colors of each k-mer, which commonly takes advantage of redundancy in the data. In many applications, such as human RNA-seq indexing  (8) , it is expected that many datasets share a large number of k-mers. This redundancy can be exploited to reduce the color encoding size, notably through color classes.
While we will not go into the technical details here (see Appendix and Supplementary Box 4 for more information), it is sufficient to see BOSS as a rearrangement of the original data that enables indexing and compression. In order to add color information in Vari, a compressed binary matrix stores which edges e i of the DBG are present in which sample s j. The matrix is constructed row-by-row, using the RRR bit vector representation for compression. A color matrix represents the presence of n k-mers across c datasets (here n = 5, c = 3). Different schemes have been introduced to encode such matrices. In particular, a color class is a set of colors (or equivalently, a bit vector, or a line in the color matrix) that is common to one or more k-mers. Indeed, in the color matrix some k-mers (lines) may correspond to the same color class.
One may "de-duplicate" the n lines of the color matrix into only m < n color classes (here, m = 4). Then, color class identifiers are introduced as intermediaries between k-mers and color classes. (To go further, frequently used color classes can be represented using fewer bits by using small integers as identifiers). Color-aggregative methods are generally composed of three parts. First, a set of all k-mers, built using either a succinct DBG or an ad-hoc representation. Second, (a) a correspondence between k-mers and colors in the form of a color matrix, color classes (b), or several color matrices (c). Finally, k-mer sets and/or colors may be further compressed (see Box 2). Later, Vari-Merge (  16 ) was introduced to construct colored DBGs for very large datasets. It first divides the data into smaller subsets, then constructs a succinct DBG (using Vari) for each, and lastly, succinctly merges then until a single one remains.
It uses a similar structure to Vari to store the k-mer set structure but stores color classes in a similar manner as in BFT. In addition, to obtain sparser bit vectors, it encodes the most frequently used classes using more zeros. As for compression, the color class and the label are represented as bit vectors that can be compressed. Mantis and Mantis+MST. Mantis (38)  introduces another strategy for storing the DBG in a space-efficient manner. (see strategy (3) in Figure  1 ). Mantis starts by building, for each dataset, an associative data structure on k-mers (CQF, see Supplementary Box 1). Initially, CQFs were introduced to record counts associated to k-mers but in Mantis, the struc-ture instead stores color sets. Mantis then merges all CQFs in order to have the global information in a global filter.
Othello hashing can yield false positives when alien k-mers are queried (i. e. , k-mers that are not present in the indexed collection). In other words, Othello hashing may wrongly associate a dataset to an alien k-mer, instead of correctly returning that such k-mer belongs to no dataset. For a query that consists of many k-mers (such as genes or transcripts) errors can be mitigated because false positives are unlikely to all point to the same dataset(s). This property will also be used in k-mer aggregative structures, and will be further discussed in a dedicated section. Bifrost, Pufferfish, and BLight Recently, another construction strategy for color-aggregation was proposed in Bifrost  (40) , which relies on two techniques: 1) in-memory construction of the DBG, 2) dynamic updates of the graph.
Background and method intuition. The design of these methods is motivated by the following use case. Let Q be a query set of k-mers to be searched in a collection of datasets D, where each element of D represents a dataset. For example, Q may be the set of k-mers contained in a single transcript. The collection D can be seen as a set of k-mer sets. One seeks to find the sets D i ∈ D such that |D i ∩ Q|/|Q| ≥ θ, with θ being a given ratio of k-mers, seen as a stringency parameter for the search. The value of θ can be set to allow for sequencing errors or mutations, e. g. between 0. 7 and 0. 9  (8). Whereas in the methods of Section 4, a query is a single kmer whose color class we would like to know, in this context, the query is a set of k-mers, and we would like to know the datasets which contain at least a θ fraction of them.
We will refer to the query of a single k-mer as a k-mer query and the query of a set of k-mers as a set query. The methods in this section take explicit advantage of the motivating use case by storing the k-mers of each dataset in a Bloom filter (BF), i. e. one BF per dataset. Recall from Section 3 that a BF is a probabilistic data structure that sometimes return false positives; i. e. the BF may report that a k-mer belongs to a certain dataset when it really does not. However, in the setting of the set query, the θ parameter allows us to naturally absorb any potentially detrimental effect of such false positives. For the values of θ used in practice, the false positive rate of a BF for k-mer queries can be as high as 50% without degradation of the set query performance  (8). Indeed, the false positive rate of a set query decreases exponentially with the number of k-mers  (8, 45).
K-mer aggregative methods summary Sequence Bloom trees SBTs are a family of related techniques detailed across multiple publications  (8, (46) (47) (48). They are an adaptation of a hierarchical index structure of BFs that was initially developed outside of bioinformatics  (49). At a high level, an SBT method builds a binary search tree (see Box 3 (a) for more details), whose leaves correspond to datasets in D and each internal node u represents the subset of D which appears as descendants of u (lets call these desc(u) ⊆ D). A set query Q starts at the root and propagates down the whole tree. At any node, the information stored at that node is used to determine which k-mers of Q have identical presence and/or absence status in all desc(u). These k-mers are then said to be determined and removed from Q as it propagates down the tree (see Box 3).
When enough k-mers become determined, the search can be pruned (i. e. not propagated further down the tree). Where the SBT methods differ is, to a large extent, in how the information at each node is stored. The initial SBT approach stored the BF of the corresponding dataset at each leaf and, at an internal node u, a BF of the union of desc(u)'s k-mers  (8). Three later works brought optimizations to the original SBT concept. The first (simultaneously discovered in  (46, 47) ) was for each node to store two BFs, one containing the k-mers present in all desc(u), and the other containing k-mers absent from all desc(u). Split-Sequence Bloom trees (SSBT)  (46)  authors also noticed that once a k-mer is stored in a BF of an internal node u, it can be removed from the BFs of u's subtree to reduce space.
BIGSI/COBS/DREAM-Yara. A radically different approach was proposed in BIGSI (12) (Box 3 (b) ). The BFs are stored in a matrix, with each column corresponding to dataset. It is useful to imagine this as the color matrix from previous sections, with the rows corresponding to the k-mers in D 1. Importantly, the matrix is stored in row-major order, i. e. row-by-row, so that each row appears as a consecutive block. Thus, a k-mer query extracts that k-mers presence or absence bit vector in D (see  Box 3). The set query Q is then answered by extracting the bit vector for each k-mer in Q and performing bitwise operations on these vectors to answer the set query. A closely related work is presented as a part of DREAM-Yara  (50) , where BFs are interleaved, in order to efficiently retrieve the same position of several BFs (see Appendix Box 9).
The false positive rate of a BF is monotonically increasing in m/n, where m is the number of k-mers in the dataset and n is the number of bits in the BF. BIGSI uses the same size n for all the BFs, thus the false positive rates of the BFs differ depending on how many k-mers are in the corresponding dataset. The idea behind COBS  (45)  is that the size of each BF (i. e. n) can be customized to its corresponding dataset, optimizing space usage while maintaining a constant false positive rate across datasets. COBS bins the datasets according to their estimated cardinality, and then uses a different BF size for each bin. COBS also improves the implementation of BIGSI and adds support for parallelization. Another advantage of COBS is that the index does not need to be fully loaded into RAM to perform queries, a feature that is also present in SBTs.
Indeed, each bin can be loaded from disk and queried separately. Detailed examples can be found in Supplementary Box 7. RAMBO Similarly to BIGSI and COBS, RAMBO stores k-mers presence or absence using several BFs in a matrix. As in SBTs, the goal is to reduce the query complexity to be sublinear in the number of datasets. But the approach radically differs from SBTs as RAMBO does not create a hierarchy of union BFs in a tree. Also, instead of simply concatenating BFs as columns of the matrix, RAMBO defines each column to be a combination (in fact, a union) of multiple BFs, corresponding to multiple k-mer sets. Since each cell now represents information from different k-mer sets (i. e. , here, the union of their BFs), some redundancy is necessary in the structure so that the original k-mer sets can be recovered.
Compression. The different flavors of SBTs optionally compress BFs in the intermediate and leaf nodes of the tree using bit vector compression (typically RRR). To our knowledge BIGSI, COBS and RAMBO make no use of compression. Insertion of new datasets. In SBTs, the insertion of a new dataset requires computing a new BF for the sample and adding this BF as a leaf to the tree. Then all the BFs on the path from that leaf to the root are updated. In BIGSI, the BF is stacked into the matrix. The COBS implementation currently does not support insertion without rebuilding the complete index. DBG traversal. Unlike color-aggregative methods, we note here that k-mer-aggregative methods do not support DBG traversal.
Other schemes. Other unpublished tools have considered different techniques for storings and indexing sets of kmer sets. kamix 2  uses samtools's BGZF compression library to store and index a k-mer matrix. From the same author, kad 3  uses a RocksDB database to store a list of k-mer and counts. Schemes based on BWT. BEETL (  51 ) is a technique that stores inside a BWT all sequences (i. e. , not k-mers, but the original data) from a sequencing dataset. BEETL was able to compress and index 135 GB of raw sequencing data into a 8. 2 GB space (on disk for storage, or in memory for queries). A variant, BEETL-fastq  (52) , also enabled to perform efficient queries and was also applied to the representation of multiple datasets. Population BWT (  53 ) is also a scheme based on BWT geared towards the indexing of thousands of raw sequencing datasets.
Section 5: Performance overview 5. 1 Index construction on human RNA-seq samples Indexing datasets of a similar type, such as RNA-seq samples from a given species, was one of the first applications proposed in the literature of sets of k-mer sets, and remains one of the main benchmarks for these tools. Table  S4  reports the performance of most of the recent tools on a collection of human RNA-seq datasets (2,652 RNA-seqs from the original SBT article  4  ). This table was extrapolated by gathering results from three recent articles  (11, 12, 48). As the articles use different hardware and slightly different parameters, a direct comparison of the tools is challenging. Instead, Table  1  presents a summary of the best possible performance that can be currently achieved on the given datasets.
Indexing bacterial genomes We now turn to the indexing of large collections of bacterial datasets. Table S5 summarizes benchmarks published in the article of COBS  (45)  and Vari-Merge  (16). The evaluated tools are SBT, SSBT, AllSomeSBT, HowDeSBT, BIGSI, COBS, Vari, Vari-Merge, Rainbowfish, BFT, Multi-BRWT and Man-tis+MST. Again we report here the best performing tool for each metric. We note that the datasets used to evaluate COBS and Vari-merge are different microbial collections, and thus, the presented results were extrapolated from different publications (see Table  S5  caption for details). Again, the more recent methods tend to perform better at all levels. BIGSI, AllSomeSBT, and COBS queries are notably fast. SSBT.
Indices In k-mer aggregative strategies, Bloom filters representing each of the initial datasets are organized in either a tree or a matrix structure. In the example below, there are four datasets (red, blue, green, and yellow), and the grey rectangles represent Bloom filters. Black bars in the BF represent the presence of k-mers. (a) Tree strategy A search tree is constructed, where each leaf is a dataset and internal nodes represent groups of datasets. Datasets with similar BFs can be clustered to reside in the same subtree. In the original SBT approach (8), each node stores exactly one BF, containing all the k-mers present in the datasets of its subtree. For a leaf, this is simply the k-mers in the corresponding dataset. Later versions of SBTs  (46) (47) (48)  store more sophisticated data at each node, though they still rely on BFs.