SUMMARY: FASTA is a widely used text-based format for storing nucleotide and protein sequences. The existing FASTA compressors usually focus on (slightly) improving the compression ratio, not on practical performance. We present FFC, a scalable FASTA compressor that achieves average compression speeds 4.7× and 11.4× higher than two high-performance compressors, zstd and NAF, respectively, across a benchmark set of seven single genomes. It also delivers average decompression speeds 3.5× and 2.7× higher than zstd and NAF, respectively. Although a chunk-based zstd variant with parallel decompression, pzstd, almost matches FFC speed, its compression ratio is on average by 23% worse than FFC's. For the experiment, a 14-core workstation and a RAM disk (to reduce the impact of I/O) were used. AVAILABILITY AND IMPLEMENTATION: FFC is freely available at github.com/kowallus/ffc and also as a Zenodo repository at 10.5281/zenodo.18892353, and the used datasets at 10.5281/zenodo.18873744.

SUMMARY: The FASTQ format remains at the heart of high-throughput sequencing. Despite advances in specialized FASTQ compressors, they are still imperfect in terms of practical performance tradeoffs. We present a multi-threaded version of Pseudogenome-based Read Compressor (PgRC), an in-memory algorithm for compressing the DNA stream, based on the idea of approximating the shortest common superstring over high-quality reads. Redundancy in the obtained string is efficiently removed by using a compact temporary representation. The current version, v2.0, preserves the compression ratio of the previous one, reducing the compression (resp. decompression) time by a factor of 8-9 (resp. 2-2.5) on a 14-core/28-thread machine. AVAILABILITY AND IMPLEMENTATION: PgRC 2.0 can be downloaded from https://github.com/kowallus/PgRC and https://zenodo.org/records/14882486 (10.5281/zenodo.14882486).

The keyboard, in a physical or virtual form, is one of the most popular and available communication mediums for computers and mobile devices. In this paper, we introduce the Keydrop, a novel virtual keyboard layout for a touchscreen that dynamically changes the keys’ labels. The results collected from 54 participants showed that Keydrop outperforms the usual QWERTY virtual keyboard in terms of typing speed and the number of typos. The solution gained positive feedback from participants, and the empirical results showed that users type 6% faster, making 33% fewer typos. The proposed solution achieves a speed of 25.17 words per minute (WPM) and 1.20 keystrokes per character (KSPC).

SUMMARY: Finding Maximum Exact Matches, i.e. matches between two strings that cannot be further extended to the left or right, is a classic string problem with applications in genome-to-genome comparisons. The existing tools rarely explicitly address the problem of MEM finding for a pair of very similar genomes, which may be computationally challenging. We present copMEM2, a multithreaded implementation of its predecessor. Together with a few optimizations, including a carefully built predecessor query data structure and sort procedure selection, and taking care for highly similar data, copMEM2 allows to compute all MEMs of minimum length 50 between the human and mouse genomes in 59 s, using 10.40 GB of RAM and 12 threads, being at least a few times faster than its main contenders. On a pair of human genomes, hg18 and hg19, the results are 324 s and 16.57 GB, respectively. AVAILABILITY AND IMPLEMENTATION: copMEM2 is available at https://github.com/wbieniec/copmem2.

A canonical Huffman code is an optimal prefix-free compression code whose codewords enumerated in the lexicographical order form a list of binary words in non-decreasing lengths. Gagie et al. (2015) gave a representation of this coding capable of encoding and decoding a symbol in constant worst-case time. It uses σlg⁡ℓmax+o(σ)+O(ℓmax2) bits of space, where σ and ℓmax are the alphabet size and maximum codeword length, respectively. We refine their representation to reduce the space complexity to σlg⁡ℓmax(1+o(1)) bits while preserving the constant encode and decode times. Our algorithmic idea can be applied to any canonical code.

Abstract All‐pairs distance computation for a collection of strings is a computation‐intensive task with important applications in bioinformatics, in particular, in distance‐based phylogenetic analysis techniques. Even if the computationally efficient Hamming distance is used for this purpose, the quadratic number of sequence pairs may be challenging. We propose a number of practical algorithms for efficient pairwise Hamming distance computation under a given distance threshold. The techniques are based on such concepts as pivot‐based similarity search in metric spaces, pigeonhole principle for approximate string matching, cache‐friendly data arrangement, bit‐parallelism, and others. We experimentally show that our solutions are often about an order of magnitude faster than the average‐case linear‐time LCP based clusters method proposed recently, both in real and synthetic benchmarks.

MOTIVATION: The amount of sequencing data from high-throughput sequencing technologies grows at a pace exceeding the one predicted by Moore's law. One of the basic requirements is to efficiently store and transmit such huge collections of data. Despite significant interest in designing FASTQ compressors, they are still imperfect in terms of compression ratio or decompression resources. RESULTS: We present Pseudogenome-based Read Compressor (PgRC), an in-memory algorithm for compressing the DNA stream, based on the idea of building an approximation of the shortest common superstring over high-quality reads. Experiments show that PgRC wins in compression ratio over its main competitors, SPRING and Minicom, by up to 15 and 20% on average, respectively, while being comparably fast in decompression. AVAILABILITY AND IMPLEMENTATION: PgRC can be downloaded from https://github.com/kowallus/PgRC. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Mapping reads to a reference genome is often the first step in a sequencing data analysis pipeline. The reduction of sequencing costs implies a need for algorithms able to process increasing amounts of generated data in reasonable time. RESULTS: We present Whisper, an accurate and high-performant mapping tool, based on the idea of sorting reads and then mapping them against suffix arrays for the reference genome and its reverse complement. Employing task and data parallelism as well as storing temporary data on disk result in superior time efficiency at reasonable memory requirements. Whisper excels at large NGS read collections, in particular Illumina reads with typical WGS coverage. The experiments with real data indicate that our solution works in about 15% of the time needed by the well-known BWA-MEM and Bowtie2 tools at a comparable accuracy, validated in a variant calling pipeline. AVAILABILITY AND IMPLEMENTATION: Whisper is available for free from https://github.com/refresh-bio/Whisper or http://sun.aei.polsl.pl/REFRESH/Whisper/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Genome-to-genome comparisons require designating anchor points, which are given by Maximum Exact Matches (MEMs) between their sequences. For large genomes this is a challenging problem and the performance of existing solutions, even in parallel regimes, is not quite satisfactory. RESULTS: We present a new algorithm, copMEM, that allows to sparsely sample both input genomes, with sampling steps being coprime. Despite being a single-threaded implementation, copMEM computes all MEMs of minimum length 100 between the human and mouse genomes in less than 2 minutes, using 7 GB of RAM memory. AVAILABILITY AND IMPLEMENTATION: https://github.com/wbieniec/copmem. SUPPLEMENTARY DATA: Supplementary data are available at Bioinformatics online.

Motivation: The many thousands of high-quality genomes available now-a-days imply a shift from single genome to pan-genomic analyses. A basic algorithmic building brick for such a scenario is online search over a collection of similar texts, a problem with surprisingly few solutions presented so far. Results: We present SOPanG, a simple tool for exact pattern matching over an elastic-degenerate string, a recently proposed simplified model for the pan-genome. Thanks to bit-parallelism, it achieves pattern matching speeds above 400 MB/s, more than an order of magnitude higher than of other software. Availability and implementation: SOPanG is available for free from: https://github.com/MrAlexSee/sopang. Supplementary information: Supplementary data are available at Bioinformatics online.

We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n, and when the input strings are run-length encoded and their compressed representations have size at most m. The alphabet size is denoted by σ. For the uncompresse d problem, we show an O(n2/ log1+1/σ n)-time and 𝒪(n)-space algorithm in the case of σ = 𝒪(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in 𝒪(m2σ2 log3m) time and 𝒪(m(σ2+log2m)) space, which employs line sweep, and one that works in 𝒪(m3) time and 𝒪(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known 𝒪(nm2)-time and 𝒪(m4)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.

Summary Range minimum query is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, practical performance and construction time also matter. Additionally, there are offline scenarios in which the number of queries, ie, q, is rather small and given beforehand, which encourages to use a simpler approach. In this work, we present a simple data structure, with very fast construction, which allows to handle queries in constant time on average. This algorithm, however, requires access to the input data during queries (which is not the case of sophisticated range minimum query solutions). We subsequently refine our technique, combining it with one of the existing succinct solutions with O(1) worst‐case time queries and no access to the input array. The resulting hybrid is still a memory frugal data structure, spending usually up to about 3n bits and providing competitive query times, especially for wide ranges. We also show how to make our baseline data structure more compact. Experimental results demonstrate that the proposed block‐based sparse table (BbST) variants are competitive to existing solutions, also in the offline scenario.

Summary Sampling (evenly) the suffixes from the suffix array is an old idea trading the pattern search time for reduced index space. A few years ago Claudeet al.showed an alphabet sampling scheme allowing for more efficient pattern searches compared with the sparse suffix array, for long enough patterns. A drawback of their approach is the requirement that sought patterns need to contain at least one character from the chosen subalphabet. In this work, we propose an alternative suffix sampling approach with only a minimum pattern length as a requirement, which is more convenient in practice. Experiments show that our algorithm (in a few variants) achieves competitive time‐space tradeoffs on most standard benchmark data. Copyright © 2017 John Wiley & Sons, Ltd.

Summary 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.

MOTIVATION: Data compression is crucial in effective handling of genomic data. Among several recently published algorithms, ERGC seems to be surprisingly good, easily beating all of the competitors. RESULTS: We evaluated ERGC and the previously proposed algorithms GDC and iDoComp, which are the ones used in the original paper for comparison, on a wide data set including 12 assemblies of human genome (instead of only four of them in the original paper). ERGC wins only when one of the genomes (referential or target) contains mixed-cased letters (which is the case for only the two Korean genomes). In all other cases ERGC is on average an order of magnitude worse than GDC and iDoComp. CONTACT: [email protected], [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Building the histogram of occurrences of every k-symbol long substring of nucleotide data is a standard step in many bioinformatics applications, known under the name of k-mer counting. Its applications include developing de Bruijn graph genome assemblers, fast multiple sequence alignment and repeat detection. The tremendous amounts of NGS data require fast algorithms for k-mer counting, preferably using moderate amounts of memory. RESULTS: We present a novel method for k-mer counting, on large datasets about twice faster than the strongest competitors (Jellyfish 2, KMC 1), using about 12 GB (or less) of RAM. Our disk-based method bears some resemblance to MSPKmerCounter, yet replacing the original minimizers with signatures (a carefully selected subset of all minimizers) and using (k, x)-mers allows to significantly reduce the I/O and a highly parallel overall architecture allows to achieve unprecedented processing speeds. For example, KMC 2 counts the 28-mers of a human reads collection with 44-fold coverage (106 GB of compressed size) in about 20 min, on a 6-core Intel i7 PC with an solid-state disk.

MOTIVATION: High-coverage sequencing data have significant, yet hard to exploit, redundancy. Most FASTQ compressors cannot efficiently compress the DNA stream of large datasets, since the redundancy between overlapping reads cannot be easily captured in the (relatively small) main memory. More interesting solutions for this problem are disk based, where the better of these two, from Cox et al. (2012), is based on the Burrows-Wheeler transform (BWT) and achieves 0.518 bits per base for a 134.0 Gbp human genome sequencing collection with almost 45-fold coverage. RESULTS: We propose overlapping reads compression with minimizers, a compression algorithm dedicated to sequencing reads (DNA only). Our method makes use of a conceptually simple and easily parallelizable idea of minimizers, to obtain 0.317 bits per base as the compression ratio, allowing to fit the 134.0 Gbp dataset into only 5.31 GB of space. AVAILABILITY AND IMPLEMENTATION: http://sun.aei.polsl.pl/orcom under a free license. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Spatial data structures, for vector or metric spaces, are a well-known means to speed-up proximity queries.One of the common uses of the found neighbors of the query object is in classification methods, e.g., the famous k-nearest neighbor algorithm.Still, most experimental works focus on providing attractive tradeoffs between neighbor search times and the neighborhood quality, but they ignore the impact of such tradeoffs on the classification accuracy.In this paper, we explore a few simple approximate and probabilistic variants of two popular spatial data structures, the k-d tree and the ball tree, with k-NN results on real data sets.The main difference between these two structures is the location of input data -in all nodes (k-d tree), or in the leaves (ball tree) -and for this reason they act as good representatives of other spatial structures.We show that in several cases significant speedups compared to the use of such structures in the exact k-NN classification are possible, with a moderate penalty in accuracy.We conclude that the usage of the k-d tree is a more promising approach.

MOTIVATION: Genomic repositories are rapidly growing, as witnessed by the 1000 Genomes or the UK10K projects. Hence, compression of multiple genomes of the same species has become an active research area in the past years. The well-known large redundancy in human sequences is not easy to exploit because of huge memory requirements from traditional compression algorithms. RESULTS: We show how to obtain several times higher compression ratio than of the best reported results, on two large genome collections (1092 human and 775 plant genomes). Our inputs are variant call format files restricted to their essential fields. More precisely, our novel Ziv-Lempel-style compression algorithm squeezes a single human genome to ∼400 KB. The key to high compression is to look for similarities across the whole collection, not just against one reference sequence, what is typical for existing solutions. AVAILABILITY: http://sun.aei.polsl.pl/tgc (also as Supplementary Material) under a free license. Supplementary data: Supplementary data are available at Bioinformatics online.

BACKGROUND: The k-mer counting problem, which is to build the histogram of occurrences of every k-symbol long substring in a given text, is important for many bioinformatics applications. They include developing de Bruijn graph genome assemblers, fast multiple sequence alignment and repeat detection. RESULTS: We propose a simple, yet efficient, parallel disk-based algorithm for counting k-mers. Experiments show that it usually offers the fastest solution to the considered problem, while demanding a relatively small amount of memory. In particular, it is capable of counting the statistics for short-read human genome data, in input gzipped FASTQ file, in less than 40 minutes on a PC with 16 GB of RAM and 6 CPU cores, and for long-read human genome data in less than 70 minutes. On a more powerful machine, using 32 GB of RAM and 32 CPU cores, the tasks are accomplished in less than half the time. No other algorithm for most tested settings of this problem and mammalian-size data can accomplish this task in comparable time. Our solution also belongs to memory-frugal ones; most competitive algorithms cannot efficiently work on a PC with 16 GB of memory for such massive data. CONCLUSIONS: By making use of cheap disk space and exploiting CPU and I/O parallelism we propose a very competitive k-mer counting procedure, called KMC. Our results suggest that judicious resource management may allow to solve at least some bioinformatics problems with massive data on a commodity personal computer.

Abstract Motivation: Modern sequencing instruments are able to generate at least hundreds of millions short reads of genomic data. Those huge volumes of data require effective means to store them, provide quick access to any record and enable fast decompression. Results: We present a specialized compression algorithm for genomic data in FASTQ format which dominates its competitor, G-SQZ, as is shown on a number of datasets from the 1000 Genomes Project (www.1000genomes.org). Availability: DSRC is freely available at http:/sun.aei.polsl.pl/dsrc. Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Storing, transferring and maintaining genomic databases becomes a major challenge because of the rapid technology progress in DNA sequencing and correspondingly growing pace at which the sequencing data are being produced. Efficient compression, with support for extraction of arbitrary snippets of any sequence, is the key to maintaining those huge amounts of data. RESULTS: We present an LZ77-style compression scheme for relative compression of multiple genomes of the same species. While the solution bears similarity to known algorithms, it offers significantly higher compression ratios at compression speed over an order of magnitude greater. In particular, 69 differentially encoded human genomes are compressed over 400 times at fast compression, or even 1000 times at slower compression (the reference genome itself needs much more space). Adding fast random access to text snippets decreases the ratio to ~300. AVAILABILITY: GDC is available at http://sun.aei.polsl.pl/gdc. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Abstract The innate verbosity of the extensible markup language (XML) remains one of its main weaknesses, especially when large documents are concerned. This problem can be solved with the aid of dedicated XML compression algorithms. In this work, we describe XML word‐replacing transform (XML‐WRT), a fast and fully reversible XML transform, which, when combined with generally used LZ77‐style compression algorithms, allows to attain high compression ratios, comparable to those achieved by the current state‐of‐the‐art XML compressors. The resulting compression scheme is asymmetric in the sense that its decoder is much faster than the coder. This is a desirable practical property, as in many XML applications data are read much more often than written. The key features of the transform are dictionary‐based encoding of both document structure and content, separation of different content types into multiple streams, and dedicated encoding of specific patterns, including numbers and dates. The test results show that the proposed transform improves the XML compression efficiency of general‐purpose compressors on average by 35% in case of gzip, and 17% in case of LZMA. Compared with the current state‐of‐the‐art SCMPPM algorithm, XML‐WRT with LZMA attains over 2% better compression ratio, while being 55% faster. Copyright © 2007 John Wiley & Sons, Ltd.

An attractive way to increase text compression is to replace words with references to a text dictionary given in advance. Although there exist a few works in this area, they do not fully exploit the compression possibilities or consider alternative preprocessing variants for various compressors in the latter phase. In this paper, we discuss several aspects of dictionary-based compression, including compact dictionary representation, and present a PPM/BWCA-oriented scheme, word replacing transformation, achieving compression ratios higher by 2–6% than the state-of-the-art StarNT (2003) text preprocessor, working at a greater speed. We also present an alternative scheme designed for LZ77 compressors, with the advantage over StarNT of reaching up to 14% in combination with gzip. Copyright © 2005 John Wiley & Sons, Ltd.

This paper presents a PPM variation which combines traditional character based processing with string matching. Such an approach can effectively handle repetitive data and can be used with practically any algorithm from the PPM family. The algorithm, inspired by its predecessors, PPM/sup */ and PPMZ, searches for matching sequences in arbitrarily long, variable-length, deterministic contexts. The experimental results show that the proposed technique may be very useful, especially in combination with relatively low order (up to 8) models, where the compression gains are often significant and the additional memory requirements are moderate.