Search

We revisit the following version of the Gapped String Indexing problem, where the goal is to preprocess a text T [ 1.. n ] to enable efficient reporting of all occ occurrences of a gapped pattern P = P 1 [ α.. β ] P 2 in T. An occurrence of P in T is defined as a pair (i , j) where substrings T [ i.. i + | P 1 |) and T [ j.. j + | P 2 |) match P 1 and P 2 , respectively, with a gap j − (i + | P 1 |) lying within the interval [ α.. β ] . This problem has significant applications in computational biology and text mining. A hardness result on this problem suggests that any index with polylogarithmic query time must occupy near quadratic space. In a recent study [STACS 2024], Bille et al. presented a sub-quadratic space index using space O ˜ (n 2 − δ / 3) , where 0 ≤ δ ≤ 1 is a parameter fixed at the time of index construction. Its query time is O ˜ (| P 1 | + | P 2 | + n δ · (1 + occ)) , which is sub-linear per occurrence when δ < 1 . We show how to achieve a gap-sensitive query time of O ˜ (| P 1 | + | P 2 | + n δ · (1 + occ 1 − δ) + ∑ g ∈ [ α.. β ] occ g · g δ) using the same space, where occ g denotes the number of occurrences with gap g. This is faster when there are many occurrences with small gaps. [ABSTRACT FROM AUTHOR]

Two recent lower bounds on the compressibility of repetitive sequences, δ ≤ γ , have received much attention. It has been shown that a length-n string S over an alphabet of size σ can be represented within the optimal O (δ log n log σ δ log n ) space, and further, that within that space one can find all the occ occurrences in S of any length-m pattern in time O (m log n + o c c log ϵ n) for any constant ϵ > 0 . Instead, the near-optimal search time O (m + (o c c + 1) log ϵ n) has been achieved only within O (γ log n γ) space. Both results are based on considerably different locally consistent parsing techniques. The question of whether the better search time could be supported within the δ -optimal space remained open. In this paper, we prove that both techniques can indeed be combined to obtain the best of both worlds: O (m + (o c c + 1) log ϵ n) search time within O (δ log n log σ δ log n ) space. Moreover, the number of occurrences can be computed in O (m + log 2 + ϵ n) time within O (δ log n log σ δ log n ) space. We also show that an extra sublogarithmic factor on top of this space enables optimal O (m + o c c) search time, whereas an extra logarithmic factor enables optimal O(m) counting time. [ABSTRACT FROM AUTHOR]

The ranked (or top-k) document retrieval problem is defined as follows: preprocess a collection {T1,T2, . . .,Td} of d strings (called documents) of total length n into a data structure, such that for any given query (P, k), where P is a string (called pattern) of length p ≥ 1 and k ∈ [1,d] is an integer, the identifiers of those k documents that are most relevant to P can be reported, ideally in the sorted order of their relevance. The seminal work by Hon et al. [FOCS 2009 and Journal of the ACM 2014] presented an O(n)-space (in words) data structure with O(p + k log k) query time. The query time was later improved to O(p + k) [SODA 2012] and further to O(p/logσ n + k) [SIAM Journal on Computing 2017] by Navarro and Nekrich, where σ is the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takes O(n)-space and answer queries in O(p/B +logB n +k/B +log ∗ (n/B)) I/Os, where B is the block size. The second one takes O(n log ∗ (n/B)) space and answer queries in optimal O(p/B + logB n + k/B) I/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top-k document retrieval, we present an O(n log(d/B)) space data structure with optimal query cost. [ABSTRACT FROM AUTHOR]

Compressed full-text indexes enable efficient sequence classification against a pangenome or tree-of-life index. Past work on compressed-index classification used matching statistics or pseudo-matching lengths to capture the fine-grained co-linearity of exact matches. But these fail to capture coarse-grained information about whether seeds appear co-linearly in the reference. We present a novel approach that additionally obtains coarse-grained co-linearity ("chain") statistics. We do this without using a chaining algorithm, which would require superlinear time in the number of matches. We start with a collection of strings, avoiding the multiple-alignment step required by graph approaches. We rapidly compute multi-maximal unique matches (multi-MUMs) and identify BWT sub-runs that correspond to these multi-MUMs. From these, we select those that can be "tunneled," and mark these with the corresponding multi-MUM identifiers. This yields an O ( r + n / d ) -space index for a collection of d sequences having a length- n BWT consisting of r maximal equal-character runs. Using the index, we simultaneously compute fine-grained matching statistics and coarse-grained chain statistics in linear time with respect to query length. We found that this substantially improves classification accuracy compared to past compressed-indexing approaches and reaches the same level of accuracy as less efficient alignment-based methods., Competing Interests: Disclosure of Interests. Ben Langmead is the founder of InOrder Labs, LLC.

Two decades ago, a breakthrough in indexing string collections made it possible to represent them within their compressed space while at the same time offering indexed search functionalities. As this new technology permeated through applications like bioinformatics, the string collections experienced a growth that outperforms Moore's Law and challenges our ability to handle them even in compressed form. It turns out, fortunately, that many of these rapidly growing string collections are highly repetitive, so that their information content is orders of magnitude lower than their plain size. The statistical compression methods used for classical collections, however, are blind to this repetitiveness, and therefore a new set of techniques has been developed to properly exploit it. The resulting indexes form a new generation of data structures able to handle the huge repetitive string collections that we are facing. In this survey, formed by two parts, we cover the algorithmic developments that have led to these data structures. In this first part, we describe the distinct compression paradigms that have been used to exploit repetitiveness, and the algorithmic techniques that provide direct access to the compressed strings. In the quest for an ideal measure of repetitiveness, we uncover a fascinating web of relations between those measures, as well as the limits up to which the data can be recovered, and up to which direct access to the compressed data can be provided. This is the basic aspect of indexability, which is covered in the second part of this survey. [ABSTRACT FROM AUTHOR]

Two decades ago, a breakthrough in indexing string collections made it possible to represent them within their compressed space while at the same time offering indexed search functionalities. As this new technology permeated through applications like bioinformatics, the string collections experienced a growth that outperforms Moore's Law and challenges our ability of handling them even in compressed form. It turns out, fortunately, that many of these rapidly growing string collections are highly repetitive, so that their information content is orders of magnitude lower than their plain size. The statistical compression methods used for classical collections, however, are blind to this repetitiveness, and therefore a new set of techniques has been developed to properly exploit it. The resulting indexes form a new generation of data structures able to handle the huge repetitive string collections that we are facing. In this survey, formed by two parts, we cover the algorithmic developments that have led to these data structures. In this second part, we describe the fundamental algorithmic ideas and data structures that form the base of all the existing indexes, and the various concrete structures that have been proposed, comparing them both in theoretical and practical aspects, and uncovering some new combinations. We conclude with the current challenges in this fascinating field. [ABSTRACT FROM AUTHOR]

Natural Language Processing (NLP) offers methods for understanding and quantifying the similarity between written documents. Within the testing industry these methods have been used for automatic item generation, automated scoring of text and speech, modeling item characteristics, automatic question answering, machine translation, and automated referencing. This paper presents research into the use of NLP for the identification of enemy and duplicate items to improve the maintenance of test item banks. Similar pairs of items can be identified using NLP, limiting the number of items content experts must review to identify enemy and duplicat items. Results from multiple testing programs show that previousely unidentified enemy pairs can be discovered with this method. [ABSTRACT FROM AUTHOR]

Let a text T [ 1.. n ] be the only string generated by a context-free grammar with g (terminal and nonterminal) symbols, and of size G (measured as the sum of the lengths of the right-hand sides of the rules). Such a grammar, called a grammar-compressed representation of T , can be encoded using G lg ⁡ G bits. We introduce the first grammar-compressed index that uses O (G lg ⁡ n) bits (precisely, G lg ⁡ n + (2 + ϵ) G lg ⁡ g for any constant ϵ > 0) and can find the occ occurrences of patterns P [ 1.. m ] in time O ((m 2 + o c c) lg ⁡ G). We implement the index and demonstrate its practicality in comparison with the state of the art, on highly repetitive text collections. [ABSTRACT FROM AUTHOR]

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11 to 2.8% of the text size, with a gain up to 50% if compared with previous solutions. [ABSTRACT FROM AUTHOR]

The FM index (Ferragina and Manzini in J ACM 52(4):552–581, 2005) is a widely-used compressed data structure that stores a string T in a compressed form and also supports fast pattern matching queries. In this paper, we describe new FM-index variants that combine nice theoretical properties, simple implementation and improved practical performance. Our main theoretical result is a new technique called fixed block compression boosting, which is a simpler and faster alternative to optimal compression boosting and implicit compression boosting used in previous FM-indexes. We also describe several new techniques for implementing fixed-block boosting efficiently, including a new, fast, and space-efficient implementation of wavelet trees. Our extensive experiments show the new indexes to be consistently fast and small relative to the state-of-the-art, and thus they make a good "off-the-shelf" choice for many applications. [ABSTRACT FROM AUTHOR]

Finding substrings of a text T that match a regular expression p is a fundamental problem. Despite being the subject of extensive research, no solution with a time complexity significantly better than O(|T||p|) has been found. Backurs and Indyk in FOCS 2016 established conditional lower bounds for the algorithmic problem based on the Strong Exponential Time Hypothesis that helps explain this difficulty. A natural question is whether we can improve the time complexity for matching the regular expression by preprocessing the text T? We show that conditioned on the Online Matrix–Vector Multiplication (OMv) conjecture, even with arbitrary polynomial preprocessing time, a regular expression query on a text cannot be answered in strongly sublinear time, i.e., O(|T|1−ε) for any ε>0. Furthermore, if we extend the OMv conjecture to a plausible conjecture regarding Boolean matrix multiplication with polynomial preprocessing time, which we call Online Matrix–Matrix Multiplication (OMM), we can strengthen this hardness result to there being no solution with a query time that is O(|T|3/2−ε). These results hold for alphabet sizes three or greater. We then provide data structures that answer queries in O(|T||p|τ) time where τ∈[1,|T|] is fixed at construction. These include a solution that works for all regular expressions with Expτ·|T| preprocessing time and space. For patterns containing only ‘concatenation’ and ‘or’ operators (the same type used in the hardness result), we provide (1) a deterministic solution which requires Expτ·|T|log2|T| preprocessing time and space, and (2) when |p|≤|T|z for z=2o(log|T|), a randomized solution with amortized query time which answers queries correctly with high probability, requiring Expτ·|T|2Ωlog|T| preprocessing time and space.

Background Labels are a way to add some information on a text, such as functional annotations such as genes on a DNA sequences. V(D)J recombinations are DNA recombinations involving two or three short genes in lymphocytes. Sequencing this short region (500 bp or less) produces labeled sequences and brings insight in the lymphocyte repertoire for onco-hematology or immunology studies. Methods We present two indexes for a text with non-overlapping labels. They store the text in a Burrows–Wheeler transform (BWT) and a compressed label sequence in a Wavelet Tree. The label sequence is taken in the order of the text (TL-index) or in the order of the BWT (TLBW-index). Both indexes need a space related to the entropy of the labeled text. Results These indexes allow efficient text–label queries to count and find labeled patterns. The TLBW-index has an overhead on simple label queries but is very efficient on combined pattern–label queries. We implemented the indexes in C++ and compared them against a baseline solution on pseudo-random as well as on V(D)J labeled texts. Discussion New indexes such as the ones we proposed improve the way we index and query labeled texts as, for instance, lymphocyte repertoire for hematological and immunological studies.

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in $$O(|P|+k)$$ time, where | P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086-1095, 2008). [ABSTRACT FROM AUTHOR]

Approximate dictionary matching (checking if a pattern occurs in a collection of strings) is a classic problem with applications in e.g. spellchecking, online catalogs, and web searchers. We present a simple solution called split index, which is based on the Dirichlet principle, for matching a keyword with few mismatches, and experimentally show that it offers competitive space-time tradeoffs. Our implementation in the C++ language is focused mostly on data compaction, which is bene cial for the search speed. We compare our solution with other algorithms and we show that it is faster when the Hamming distance is used. Query times in the order of 1 microsecond were reported for one mismatch for a few-megabyte natural language dictionary on a medium-end PC. We also demonstrate that a basic compression technique consisting in q-gram substitution can signi cantly reduce the index size (up to 50% of the input text size for the DNA sequences). [ABSTRACT FROM AUTHOR]

We consider the problem of indexing a given text T [ 0 . . . n − 1 ] of n characters over an alphabet set Σ of size σ , in order to answer the position-restricted substring searching queries. The query input consists of a pattern P (of length p ) and two indices ℓ and r and the output is the set of all o c c ℓ , r occurrences of P in T [ ℓ . . . r ] . In this paper, we propose an O ( n log ⁡ σ ) -word space index with O ( p + o c c ℓ , r log ⁡ log ⁡ n ) query time. Our solution is interesting when the alphabet size is small. For example, when the alphabet set is of constant size, we achieve significant improvement over the previously best-known linear space index by Navarro and Nekrich [SWAT 2012] with O ( p + o c c ℓ , r log ϵ ⁡ n ) query time, where ϵ > 0 is an arbitrarily small positive constant. [ABSTRACT FROM AUTHOR]

We present a simple q-gram based semi-index, which allows to look for a pattern typically only in a small fraction of text blocks. Several space-time tradeoffs are presented. Experiments on Pizza & Chili datasets show that our solution is up to three orders of magnitude faster than the Claude et al. (Journal of Discrete Algorithms 2012; 11:37) semi-index at a comparable space usage. Moreover, the construction of our data structure is fast and easily parallelizable. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Background: 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 l each, on an alphabet of total size σ, our algorithms take O(n(t + log σ)) time and just 2n + o(n) + O(max{lσ log n, 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 ar [ABSTRACT FROM AUTHOR]