Efficient information retrieval is a fundamental requirement in a wide array of applications, ranging from bioinformatics to database systems, and critically hinges on the complexity of an underlying distance metric. This work presents a novel approach to compute Levenshtein embeddings within Euclidean spaces by leveraging transformer-based models to obtain string embeddings with low distortion. L 2 embeddings of Levenshtein distance in 64-dimensions for sequences of length up to 256 are obtained by means of coarse-to-fine convolutions of learned 1,2,4-mer embeddings of the original string fed into transformer encoder stacks. These embeddings are shown to facilitate efficient retrieval and clustering processes, as well as to improve reference-based compression techniques by accelerating the search for similar sequences. Different type of experiments report: (1) the distortion of the embeddings, which characterizes the fidelity to the original Levenshtein metric by comparing the original distance with the estimated one between the corresponding L 2 embeddings; (2) the performance of top- k similar string retrieval, which assesses Jaccard similarity to verify the precision of the embedding space; (3) how well k -means over string embeddings approximates k -medoid clustering, with a comparative analysis against ground truth medoids, to evaluate the clustering efficiency of the embeddings; (4) the quality of reference-based compression, implemented by projecting a dataset of strings into the embedding space, computing a k-means clustering, and compressing the payload formed by concatenating cluster centers and the alignment tracebacks of each string to its assigned cluster center. Results of these preliminary experiments indicate that these embeddings (1) present low distortion for the target applications; (2) can be used to retrieve similar strings from a dataset of 10, 50, 100 random clusters with 40 strings per cluster, with inter-cluster distances of 5, 10, 25, 50; of strings of length 100 with more than 0.92 Jaccard similarity, (3) result in an "elbow" pattern in the inertia of the k-means clustering mirroring that of the k-medoid approximation with increasing k, and (4) achieve adequate reference based-compression through k-means clustering, with performance depending on the underlying distribution of the string dataset. These findings confirm that these string embeddings could be used to build tools for improving information retrieval in several domains.

We introduce an extension of the Burrows-Wheeler transform supporting exact pattern matching on a string graph $G(V,\ E,\ N)$ and yielding polynomial time queries.

Genomic sequencing data contain three different data fields: read names, quality values, and nucleotide sequences. In this work, a variety of entropy encoders and com-pression algorithms were benchmarked in terms of compression-decompression rates and times separately for each data field as raw data from FASTQ files (implemented in the Fastq analysis script) and in MPEG-G uncompressed descriptor symbols de-coded from MPEG-G bitstreams (implemented in the symbols analysis script). The result of this benchmark is then compared to the performance of CABAC, which is the encoder used in first edition of the ISO /IEC MPEG-G standard for all types of descriptors, since CABAC was the best performing in terms of compression rates for the three types of data, thus providing overall better compression rates compared to other entropy coders in total. However, in some use cases encoding and decoding speed might be of higher interest than compression, and for specific datasets, types of data, or descriptor streams, other entropy coders might provide higher speed and/or better compression performance than CABAC.

With the widespread application of next generation sequencing technologies, the volume of sequencing data became comparable to that of big data domains. The compression of sequencing reads (nucleotide sequences, quality values, read names), in both raw and aligned data, is a way to alleviate bandwidth, transfer, and storage requirements of genomics pipelines. ISO/IEC MPEG-G standardizes the compressed representation (i.e. storage and streaming) of structured, indexed sets of genomic sequencing data for both raw and aligned data. For the latter, reference-based compression is a strategy used to compress nucleotide sequences of sequencing reads by using alignment information to a reference sequence, which can be used to represent nucleotide sequences by storing the starting position of the alignment on the reference sequence, and the differences between the reference and the actual read. This general scheme is implemented in different ways by genomic data compressors, such as DeeZ, Quip, and CRAM, which apply to aligned reads.