The Metric Suffix Array (MSA) is a variant of the classical suffix array designed to support similarity queries over multimedia data. It is a permutation-base index that stores lists of objects ranked by their similarity to a set of reference objects. In this paper, we present two compact alternatives for representing the Metric Suffix Array using less space. The first uses variable-length integer encoding to store the difference between consecutive values in MSA buckets, which are decoded during the queries with a small overhead in time. The second encodes the values in the concatenated ranking list using a Wavelet tree, allowing to obtain MSA values without explicitly computing them. All compact data structures are constructed directly from the input data without the need to compute the complete MSA beforehand, thereby enabling the indexing of much larger data volumes. Experimental results with high-dimensional features extracted from 64 million images showed that our compact alternatives require less than 25% of the original method’s total memory while increasing the query execution time by a small constant factor.

The Lyndon Array (LA) is an important data structure that gives the length of the longest Lyndon word starting at every position of a string S . LMS-based grammar compression consists of building a context-free grammar that generates only the input string, having LMS-substrings as the right side of the rules. In this paper, we show how to compute the LA during the decompression of GCIS (Nunes et al., ACM J. Exp. Algorithmics, 2022), an LMS-based compressor that achieves competitive compression ratios and is faster than popular grammar compressors. For highly repetitive sequences, GCIS grammars require only a small fraction of the input size. Although the algorithms we introduce in this paper are slower than the algorithm by Bille et al. (ICALP, 2020), when constructing the LA from compressed text one of our algorithms uses 20% less memory than first decompressing and then computing the LA. Apart from algorithmic interest, this work add tools for LA construction that enable selecting different tradeoffs between decompression space and time, preserving the advantages on disk storage and network bandwidth usage provided by GCIS, and may be particularly useful on very large datasets.

BACKGROUND: The development of Next Generation Sequencing (NGS) has had a major impact on the study of genetic sequences. Among problems that researchers in the field have to face, one of the most challenging is the taxonomic classification of metagenomic reads, i.e., identifying the microorganisms that are present in a sample collected directly from the environment. The analysis of environmental samples (metagenomes) are particularly important to figure out the microbial composition of different ecosystems and it is used in a wide variety of fields: for instance, metagenomic studies in agriculture can help understanding the interactions between plants and microbes, or in ecology, they can provide valuable insights into the functions of environmental communities. RESULTS: In this paper, we describe a new lightweight alignment-free and assembly-free framework for metagenomic classification that compares each unknown sequence in the sample to a collection of known genomes. We take advantage of the combinatorial properties of an extension of the Burrows-Wheeler transform, and we sequentially scan the required data structures, so that we can analyze unknown sequences of large collections using little internal memory. The tool LiME (Lightweight Metagenomics via eBWT) is available at https://github.com/veronicaguerrini/LiME . CONCLUSIONS: In order to assess the reliability of our approach, we run several experiments on NGS data from two simulated metagenomes among those provided in benchmarking analysis and on a real metagenome from the Human Microbiome Project. The experiment results on the simulated data show that LiME is competitive with the widely used taxonomic classifiers. It achieves high levels of precision and specificity - e.g. 99.9% of the positive control reads are correctly assigned and the percentage of classified reads of the negative control is less than 0.01% - while keeping a high sensitivity. On the real metagenome, we show that LiME is able to deliver classification results comparable to that of MagicBlast. Overall, the experiments confirm the effectiveness of our method and its high accuracy even in negative control samples.

We introduce GCIS, a grammar compression algorithm based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. Our solution builds on the factorization performed by SAIS during suffix sorting. We construct a context-free grammar on the input string which can be further reduced into a shorter string by substituting each substring by its corresponding factor. The resulting grammar is encoded by exploring some redundancies, such as common prefixes between suffix rules, which are sorted according to SAIS framework. When compared to well-known compression tools such as Re-Pair and 7-zip under repetitive sequences, our algorithm is faster at compressing and achieves compression ratio close to that of Re-Pair, at the cost of being the slowest at decompressing.

We propose an external memory algorithm for the computation of the BWT and LCP array for a collection of sequences. Our algorithm takes the amount of available memory as an input parameter, and tries to make the best use of it by splitting the input collection into subcollections sufficiently small that it can compute their BWT in RAM using an optimal linear time algorithm. Next, it merges the partial BWTs in external memory and in the process it also computes the LCP values. We prove that our algorithm performs O(n AveLcp) sequential I/Os, where n is the total length of the collection, and AveLcp is the average Longest Common Prefix of the collection. This bound is an improvement over the known algorithms for the same task. The experimental results show that our algorithm outperforms the current best algorithm for collections of sequences with different lengths and for collections with relatively small average Longest Common Prefix. In the second part of the paper, we show that our algorithm can be modified to output two additional arrays that, used with the BWT and LCP arrays, provide simple, scan based, external memory algorithms for three well known problems in bioinformatics: the computation of maximal repeats, the all pairs suffix-prefix overlaps, and the construction of succinct de Bruijn graphs. To our knowledge, there are no other known external memory algorithms for these problems.

Sorting all suffixes of a string collection may be performed by sorting the concatenation of all strings using different end marker symbols as separators, or alternatively using the same end marker as separator. However, both approaches have the following drawbacks. The first alternative increases the alphabet size of the resulting string by the number of strings, whereas the second alternative does not guarantee the order among suffixes that are equal up to the end marker symbol. In this article, we show how to modify two important suffix sorting algorithms, SAIS [1] and SACA-K [2], to sort the concatenated string using the same end marker, maintaining their theoretical bounds, respecting the order among all suffixes, and improving their practical performance.