International Journal Papers
Permanent URI for this collectionhttp://dl.cerist.dz/handle/CERIST/17
Browse
10 results
Search Results
Item Range Majorities and Minorities in Arrays(Springer Nature, 2021-03-19) Belazzougui, Djamal; Gagie, Travis; Munro, J. Ian; Navarro, Gonzalo; Nekrich, YakovThe problem of parameterized range majority asks us to preprocess a string of length n such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold τ. This is a more tractable version of the classical problem of finding the range mode, which is unlikely to be solvable in polylogarithmic time and linear space. In this paper we give the first linear-space solution with optimal 𝓞(1/τ ) query time, even when τ can be specified with the query. We then consider data structures whose space is bounded by the entropy of the distribution of the symbols in the sequence. For the case when the alphabet size is polynomial on the computer word size, we retain the optimal time within optimally compressed space (i.e., with sublinear redundancy). Otherwise, either the compressed space is increased by an arbitrarily small constant factor or the time rises to any function in (1/τ ) · ω(1). We obtain the same results on the complementary problem of parameterized range minority.Item Block Trees(ELSEVIER, 2021-05) Belazzougui, Djamal; Cáceres, Manuel; Gagie, Travis; Gawrychowski, Paweł; Kärkkäinen, Juha; Navarro, Gonzalo; Ordóñez, Alberto; Puglisi, Simon J.; Tabei, YasuoLet string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes S in 𝒪(z) space, but it does not support random access to S. We introduce a data structure, the block tree, that represents S in 𝒪(z log(n/z)) space and extracts any symbol of T in time 𝒪(log(n/z)), among other space-time tradeoffs. By multiplying the space by the alphabet size, we also support rank and select queries, which are useful for building compressed data structures on top of S. Further, block trees can be built in a scalable manner. Our experiments show that block trees offer relevant space-time tradeoffs compared to other compressed string representations for highly repetitive strings.Item Linear-time string indexing and analysis in small space(Association for Computing Machinery, 2020-03-09) Belazzougui, Djamal; Cunial, Fabio; Kärkkäinen, Juha; Mäkinen, VeliThe field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. For example, one can compare two genomes by building a common index for their concatenation, and by detecting common substructures by querying the index. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string T ∈ {1, . . . ,σ }^n can be built in deterministic O (n) time using just O (n log σ ) bits of space, where σ ≤ n. Deterministic linear time is achieved by exploiting a new partial rank data structure that supports queries in constant time, and that might have independent interest. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of T . Many fundamental string analysis problems, such as maximal repeats, maximal unique matches, and string kernels, can be mapped to such enumeration, and can thus be solved in deterministic O (n) time and in O (n log σ ) bits of space from the input string, by tailoring the enumeration algorithm to some problem-specific computations. We also show how to build many of the existing indexes based on the BWT, such as the compressed suffix array, the compressed suffix tree, and the bidirectional BWT index, in randomized O (n) time and in O (n log σ ) bits of space. The previously fastest construction algorithms for BWT, compressed suffix array and compressed suffix tree, which used O (n log σ ) bits of space, took O (n log log σ ) time for the first two structures, and O (n log^ϵ n) time for the third, where ϵ is any positive constant smaller than one. Alternatively, the BWT could be previously built in linear time if one was willing to spend O (n log σ log log_σ n) bits of space. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output.Item A framework for space-efficient variable-order Markov models(Oxford University Press, 2019-11-15) Cunial, Fabio; Alanko, Jarno; Belazzougui, DjamalMotivation: Markov models with contexts of variable length are widely used in bioinformatics for representing sets of sequences with similar biological properties. When models contain many long contexts, existing implementations are either unable to handle genome-scale training datasets within typical memory budgets, or they are optimized for specific model variants and are thus inflexible. Results: We provide practical, versatile representations of variable-order Markov models and of interpolated Markov models, that support a large number of context-selection criteria, scoring functions, probability smoothing methods, and interpolations, and that take up to four times less space than previous implementations based on the suffix array, regardless of the number and length of contexts, and up to ten times less space than previous trie-based representations, or more, while matching the size of related, state-of-the-art data structures from Natural Language Processing. We describe how to further compress our indexes to a quantity related to the redundancy of the training data, saving up to 90% of their space on very repetitive datasets, and making them become up to sixty times smaller than previous implementations based on the suffix array. Finally, we show how to exploit constraints on the length and frequency of contexts to further shrink our compressed indexes to half of their size or more, achieving data structures that are a hundred times smaller than previous implementations based on the suffix array, or more. This allows variable-order Markov models to be used with bigger datasets and with longer contexts on the same hardware, thus possibly enabling new applications. Availability and implementation: https://github.com/jnalanko/VOMMItem Bidirectional Variable-Order de Bruijn Graphs(World Scientific Publishing, 2018-12) Belazzougui, Djamal; Gagie, Travis; Mäkinen, Veli; Previtali, Marco; Puglisi, Simon J.Compressed suffix trees and bidirectional FM-indexes can store a set of strings and support queries that let us explore the set of substrings they contain, adding and deleting characters on both the left and right, but they can use much more space than a de Bruijn graph for the strings. Bowe et al.’s BWT-based de Bruijn graph representation (Proc. Workshop on Algorithms for Bioinformatics, pp. 225–235, 2012) can be made bidirectional as well, at the cost of increasing its space usage by a small constant, but it fixes the length of the substrings. Boucher et al. (Proc. Data Compression Conference, pp. 383–392, 2015) generalized Bowe et al.’s representation to support queries about variable-length substrings, but at the cost of bidirectionality. In this paper we show how to make Boucher et al.’s variable-order implementation of de Bruijn graphs bidirectional.Item Memory-Efficient and Ultra-Fast Network Lookup and Forwarding Using Othello Hashing(IEEE, 2018-04-11) Yu, Ye; Belazzougui, Djamal; Qian, Chen; Zhang, QinAbstract: Network algorithms always prefer low memory cost and fast packet processing speed. Forwarding information base (FIB), as a typical network processing component, requires a scalable and memory-efficient algorithm to support fast lookups. In this paper, we present a new network algorithm, Othello hashing, and its application of a FIB design called concise, which uses very little memory to support ultra-fast lookups of network names. Othello hashing and concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource-rich control plane. We implemented concise on three platforms. Experimental results show that concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.Item A Framework for Space-Efficient String Kernels(Springer, 2017-02-17) Belazzougui, Djamal; Cunial, FabioString kernels are typically used to compare genome-scale sequences whose length makes alignment impractical, yet their computation is based on data structures that are either space-inefficient, or incur large slowdowns. We show that a number of exact kernels on pairs of strings of total length n, like the k-mer kernel, the substrings kernels, a number of length-weighted kernels, the minimal absent words kernel, and kernels with Markovian corrections, can all be computed in O(nd) time and in o(n) bits of space in addition to the input, using just a rangeDistinct data structure on the Burrows–Wheeler transform of the input strings that takes O(d) time per element in its output. The same bounds hold for a number of measures of compositional complexity based on multiple values of k, like the k-mer profile and the k-th order empirical entropy, and for calibrating the value of k using the data. All such algorithms become O(n) using a suitable implementation of the rangeDistinct data structure, and by concatenating them to a suitable BWT construction algorithm, we can compute all the mentioned kernels and complexity measures, directly from the input strings, in O(n) time and in O(n log σ) bits of space in addition to the input, where σ is the size of the alphabet. Using similar data structures, we also show how to build a compact representation of the variable-length Markov chain of a string T of length n, that takes just 3n log σ+o(n log σ) bits of space, and that can be learnt in randomized O(n) time using O(n log σ) bits of space in addition to the input. Such model can then be used to assign a probability to a query string S of length m in O(m) time and in 2m+o(m) bits of additional space, thus providing an alternative, compositional measure of the similarity between S and T that does not require alignment.Item A framework for space-efficient read clustering in metagenomic samples(BioMed Central, 2017-03-14) Alanko, Jarno; Cunial, Fabio; Belazzougui, Djamal; Mäkinen, VeliBackground: A metagenomic sample is a set of DNA fragments, randomly extracted from multiple cells in an environment, belonging to distinct, often unknown species. Unsupervised metagenomic clustering aims at partitioning a metagenomic sample into sets that approximate taxonomic units, without using reference genomes. Since samples are large and steadily growing, space-efficient clustering algorithms are strongly needed. Results: We design and implement a space-efficient algorithmic framework that solves a number of core primitives in unsupervised metagenomic clustering using just the bidirectional Burrows-Wheeler index and a union-find data structure on the set of reads. When run on a sample of total length n, with m reads of maximum length ℓ each, on an alphabet of total size σ, our algorithms take O(n(t+logσ)) time and just 2n+o(n)+O(max{ℓ σlogn,K logm}) bits of space in addition to the index and to the union-find data structure, where K is a measure of the redundancy of the sample and t is the query time of the union-find data structure. Conclusions: Our experimental results show that our algorithms are practical, they can exploit multiple cores by a parallel traversal of the suffix-link tree, and they are competitive both in space and in time with the state of the art.Item Indexing and querying color sets of images(Springer Varlag, 2016-09-27) Belazzougui, Djamal; Kolpakov, Roman; Raffinot, MathieuWe aim to study the set of color sets of continuous regions of an image given as a matrix of m rows over n ≥ m columns where each element in the matrix is an integer from [1,σ] named a color . The set of distinct colors in a region is called fingerprint. We aim to compute, index and query the fingerprints of all rectangular regions named rectangles. The set of all such fingerprints is denoted by F. A rectangle is maximal if it is not contained in a greater rectangle with the same fingerprint. The set of all locations of maximal rectangles is denoted by L. We first explain how to determine all the |L| maximal locations with their fingerprints in expected time O(n⋅m^2⋅σ) using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic O(n⋅m^2⋅σ⋅log(|L|/(n⋅m^2)+2)) time. We then show how to build a data structure which occupies O(n⋅m⋅log n+|L|) space such that a query which asks for all the maximal locations with a given fingerprint f can be answered in time O(|f|+log log n+k), where k is the number of maximal locations with fingerprint f. If the query asks only for the presence of the fingerprint, then the space usage becomes O(n⋅m⋅log n+|F|) while the query time becomes O(|f|+log log n). We eventually consider the special case of squared regions (squares).Item Optimal Las Vegas reduction from one-way set reconciliation to error correction(Springer Varlag, 2016-03-28) Belazzougui, DjamalSuppose we have two players A and C, where player A has a string s[0..u−1] and player C has a string t[0..u−1] and none of the two players knows the other's string. Assume that s and t are both over an integer alphabet [σ]=[0,σ−1], where the first string contains n non-zero entries. We would wish to answer the following basic question. Assuming that s and t differ in at most k positions, how many bits does player A need to send to player C so that he can recover s with certainty? Further, how much time does player A need to spend to compute the sent bits and how much time does player C need to recover the string s? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of n key-value pairs, where keys are from the universe [u]=[0,u-1] and values are from [σ] and usually n ≪ u. In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of k errors for strings of length Θ(n) over an alphabet of size 2^{Θ(log σ+log(u/n))}. The additional running time incurred by the reduction is linear expected (randomized) for player A and linear worst-case (deterministic) for player C , but the correction works with certainty. When using the popular Reed–Solomon codes, the reduction gives a protocol that transmits O(k(log u+log σ)) bits and runs in time O(n⋅polylog(n)(log u+log σ)) for all values of k. The time is expected for player A (encoding time) and worst-case for player C (decoding time). The message size is optimal whenever k ≤ (u⋅σ)^{1−Ω(1)}.