CNR Author
operator:
and / or
Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2024
Journal article
Open Access
Where the patterns are: repetition-aware compression for colored de Bruijn graphs
Campanelli A., Pibiri G. E., Fan J., Patro R.
We describe lossless compressed data structures for the colored de Bruijn graph (or c-dBG). Given a collection of reference sequences, a c-dBG can be essentially regarded as a map from k-mers to their color sets. The color set of a k-mer is the set of all identifiers, or colors, of the references that contain the k-mer. While these maps find countless applications in computational biology (e.g., basic query, reading mapping, abundance estimation, etc.), their memory usage represents a serious challenge for large-scale sequence indexing. Our solutions leverage on the intrinsic repetitiveness of the color sets when indexing large collections of related genomes. Hence, the described algorithms factorize the color sets into patterns that repeat across the entire collection and represent these patterns once instead of redundantly replicating their representation as would happen if the sets were encoded as atomic lists of integers. Experimental results across a range of datasets and query workloads show that these representations substantially improve over the space effectiveness of the best previous solutions (sometimes, even dramatically, yielding indexes that are smaller by an order of magnitude). Despite the space reduction, these indexes only moderately impact the efficiency of the queries compared to the fastest indexes.Source: JOURNAL OF COMPUTATIONAL BIOLOGY
DOI: 10.1089/cmb.2024.0714
DOI: 10.1101/2024.07.09.602727
Project(s): EFRA
Metrics:
Campanelli A., Pibiri G. E., Fan J., Patro R.
We describe lossless compressed data structures for the colored de Bruijn graph (or c-dBG). Given a collection of reference sequences, a c-dBG can be essentially regarded as a map from k-mers to their color sets. The color set of a k-mer is the set of all identifiers, or colors, of the references that contain the k-mer. While these maps find countless applications in computational biology (e.g., basic query, reading mapping, abundance estimation, etc.), their memory usage represents a serious challenge for large-scale sequence indexing. Our solutions leverage on the intrinsic repetitiveness of the color sets when indexing large collections of related genomes. Hence, the described algorithms factorize the color sets into patterns that repeat across the entire collection and represent these patterns once instead of redundantly replicating their representation as would happen if the sets were encoded as atomic lists of integers. Experimental results across a range of datasets and query workloads show that these representations substantially improve over the space effectiveness of the best previous solutions (sometimes, even dramatically, yielding indexes that are smaller by an order of magnitude). Despite the space reduction, these indexes only moderately impact the efficiency of the queries compared to the fastest indexes.Source: JOURNAL OF COMPUTATIONAL BIOLOGY
DOI: 10.1089/cmb.2024.0714
DOI: 10.1101/2024.07.09.602727
Project(s): EFRA
Metrics:
See at:
Archivio istituzionale della ricerca - Università degli Studi di Venezia Ca' Foscari 
| Archivio istituzionale della ricerca - Università degli Studi di Venezia Ca' Foscari | IRIS Cnr | IRIS Cnr | Journal of Computational Biology 
| doi.org | CNR IRIS | CNR IRIS
2024
Conference article
Open Access
PHOBIC: Perfect Hashing with Optimized Bucket sizes and Interleaved Coding
Hermann S., Lehmann H. -P., Pibiri G. E., Sanders P., Walzer S.
A minimal perfect hash function (or MPHF) maps a set of n keys to [n]:= {1, ..., n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In this paper we revisit PTHash - a construction technique particularly designed for fast queries. PTHash distributes the input keys into small buckets and, for each bucket, it searches for a hash function seed that places its keys in the output domain without collisions. The collection of all seeds is then stored in a compressed way. Since the first buckets are easier to place, buckets are considered in non-increasing order of size. Additionally, PTHash heuristically produces an imbalanced distribution of bucket sizes by distributing 60% of the keys into 30% of the buckets. Our main contribution is to characterize, up to lower order terms, an optimal choice for the expected bucket sizes, improving construction throughput for space efficient configurations both in theory and practice. Further contributions include a new encoding scheme for seeds that works across partitions of the data structure and a GPU parallelization. Compared to PTHash, PHOBIC is 0.17 bits/key more space efficient for same query time and construction throughput. For a configuration with fast queries, our GPU implementation can construct an MPHF at 2.17 bits/key in 28 ns/key, which can be queried in 37 ns/query on the CPU.Source: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, vol. 308. London, UK, 02-04/09/2024
DOI: 10.4230/lipics.esa.2024.69
Project(s): EFRA
Metrics:
Hermann S., Lehmann H. -P., Pibiri G. E., Sanders P., Walzer S.
A minimal perfect hash function (or MPHF) maps a set of n keys to [n]:= {1, ..., n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In this paper we revisit PTHash - a construction technique particularly designed for fast queries. PTHash distributes the input keys into small buckets and, for each bucket, it searches for a hash function seed that places its keys in the output domain without collisions. The collection of all seeds is then stored in a compressed way. Since the first buckets are easier to place, buckets are considered in non-increasing order of size. Additionally, PTHash heuristically produces an imbalanced distribution of bucket sizes by distributing 60% of the keys into 30% of the buckets. Our main contribution is to characterize, up to lower order terms, an optimal choice for the expected bucket sizes, improving construction throughput for space efficient configurations both in theory and practice. Further contributions include a new encoding scheme for seeds that works across partitions of the data structure and a GPU parallelization. Compared to PTHash, PHOBIC is 0.17 bits/key more space efficient for same query time and construction throughput. For a configuration with fast queries, our GPU implementation can construct an MPHF at 2.17 bits/key in 28 ns/key, which can be queried in 37 ns/query on the CPU.Source: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, vol. 308. London, UK, 02-04/09/2024
DOI: 10.4230/lipics.esa.2024.69
Project(s): EFRA
Metrics:
See at:
drops.dagstuhl.de | CNR IRIS | CNR IRIS
2024
Journal article
Open Access
Fulgor: a fast and compact k-mer index for large-scale matching and color queries
Fan J, Khan J, Pratap Singh N, Pibiri Ge, Patro R
The problem of sequence identification or matching--determining the subset of reference sequences from a givencollection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasksin Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analysesand 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 efficientto query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficientcolored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. Theproposed 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 keptin the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as littleas 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. Bycombining this property with simple but effective compression methods for integer lists, the index achieves verysmall space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysisto demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--thestrongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (upto 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× faster to construct.Source: ALGORITHMS FOR MOLECULAR BIOLOGY, vol. 19 (issue 3)
DOI: 10.1186/s13015-024-00251-9
Metrics:
Fan J, Khan J, Pratap Singh N, Pibiri Ge, Patro R
The problem of sequence identification or matching--determining the subset of reference sequences from a givencollection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasksin Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analysesand 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 efficientto query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficientcolored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. Theproposed 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 keptin the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as littleas 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. Bycombining this property with simple but effective compression methods for integer lists, the index achieves verysmall space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysisto demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--thestrongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (upto 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× faster to construct.Source: ALGORITHMS FOR MOLECULAR BIOLOGY, vol. 19 (issue 3)
DOI: 10.1186/s13015-024-00251-9
Metrics:
See at:
almob.biomedcentral.com | CNR IRIS | ISTI Repository | CNR IRIS
2024
Conference article
Open Access
The {mod-minimizer}: a simple and efficient sampling algorithm for long k-Mers
Koerkamp R. G., Pibiri G. E.
Motivation. Given a string S, a minimizer scheme is an algorithm defined by a triple (k,w,O) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the smallest k-mer according to the order O from each window of w consecutive k-mers in S. Because consecutive windows can sample the same k-mer, the set of the sampled k-mers is typically much smaller than S. More generally, we consider substring sampling algorithms that respect a window guarantee: at least one k-mer must be sampled from every window of w consecutive k-mers. As a sampled k-mer is uniquely identified by its absolute position in S, we can define the density of a sampling algorithm as the fraction of distinct sampled positions. Good methods have low density which, by respecting the window guarantee, is lower bounded by 1/w. It is however difficult to design a sequence-agnostic algorithm with provably optimal density. In practice, the order O is usually implemented using a pseudo-random hash function to obtain the so-called random minimizer. This scheme is simple to implement, very fast to compute even in streaming fashion, and easy to analyze. However, its density is almost a factor of 2 away from the lower bound for large windows. Methods. In this work we introduce mod-sampling, a two-step sampling algorithm to obtain new minimizer schemes. Given a (small) parameter t, the mod-sampling algorithm finds the position p of the smallest t-mer in a window. It then samples the k-mer at position pod w. The lr-minimizer uses t = k-w and the mod-minimizer uses t≡ k (mod w). Results. These new schemes have provably lower density than random minimizers and other schemes when k is large compared to w, while being as fast to compute. Importantly, the mod-minimizer achieves optimal density when k → ∞. Although the mod-minimizer is not the first method to achieve optimal density for large k, its proof of optimality is simpler than previous work. We provide pseudocode for a number of other methods and compare to them. In practice, the mod-minimizer has considerably lower density than the random minimizer and other state-of-the-art methods, like closed syncmers and miniception, when k > w. We plugged the mod-minimizer into SSHash, a k-mer dictionary based on minimizers. For default parameters (w,k) = (11,21), space usage decreases by 15% when indexing the whole human genome (GRCh38), while maintaining its fast query time.Source: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, vol. 312. Royal Holloway, London, United Kingdom, 2-4/09/2024
DOI: 10.4230/lipics.wabi.2024.11
Metrics:
Koerkamp R. G., Pibiri G. E.
Motivation. Given a string S, a minimizer scheme is an algorithm defined by a triple (k,w,O) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the smallest k-mer according to the order O from each window of w consecutive k-mers in S. Because consecutive windows can sample the same k-mer, the set of the sampled k-mers is typically much smaller than S. More generally, we consider substring sampling algorithms that respect a window guarantee: at least one k-mer must be sampled from every window of w consecutive k-mers. As a sampled k-mer is uniquely identified by its absolute position in S, we can define the density of a sampling algorithm as the fraction of distinct sampled positions. Good methods have low density which, by respecting the window guarantee, is lower bounded by 1/w. It is however difficult to design a sequence-agnostic algorithm with provably optimal density. In practice, the order O is usually implemented using a pseudo-random hash function to obtain the so-called random minimizer. This scheme is simple to implement, very fast to compute even in streaming fashion, and easy to analyze. However, its density is almost a factor of 2 away from the lower bound for large windows. Methods. In this work we introduce mod-sampling, a two-step sampling algorithm to obtain new minimizer schemes. Given a (small) parameter t, the mod-sampling algorithm finds the position p of the smallest t-mer in a window. It then samples the k-mer at position pod w. The lr-minimizer uses t = k-w and the mod-minimizer uses t≡ k (mod w). Results. These new schemes have provably lower density than random minimizers and other schemes when k is large compared to w, while being as fast to compute. Importantly, the mod-minimizer achieves optimal density when k → ∞. Although the mod-minimizer is not the first method to achieve optimal density for large k, its proof of optimality is simpler than previous work. We provide pseudocode for a number of other methods and compare to them. In practice, the mod-minimizer has considerably lower density than the random minimizer and other state-of-the-art methods, like closed syncmers and miniception, when k > w. We plugged the mod-minimizer into SSHash, a k-mer dictionary based on minimizers. For default parameters (w,k) = (11,21), space usage decreases by 15% when indexing the whole human genome (GRCh38), while maintaining its fast query time.Source: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, vol. 312. Royal Holloway, London, United Kingdom, 2-4/09/2024
DOI: 10.4230/lipics.wabi.2024.11
Metrics:
See at:
drops.dagstuhl.de | CNR IRIS | CNR IRIS