; a minimizer digest; ■ a KATKA kernel of a minimizer digest. With a test dataset and these three representations of it, simulated reads and various parameter settings, we checked how many reads' longest MEMs occurred only in the sequences from which those reads were generated ("true positive" reads). For some parameter settings we achieved significant compression while only slightly decreasing the true-positive rate.

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string S, it produces a dictionary D and a parse P of overlapping phrases such that BWT(S) can be computed from D and P in time and workspace bounded in terms of their combined size |PFP(S)|. In practice D and P are significantly smaller than S and computing BWT(S) from them is more efficient than computing it from S directly, at least when S is the concatenation of many genomes. In this paper, we consider PFP(S) as a data structure and show how it can be augmented to support full suffix tree functionality, still built and fitting within O(|PFP(S)|) space. This entails the efficient computation of various primitives to simulate the suffix tree: computing a longest common extension (LCE) of two positions in S; reading any cell of its suffix array (SA), of its inverse (ISA), of its BWT, and of its longest common prefix array (LCP); and computing minima over ranges and next/previous smaller value queries over the LCP. Our experimental results show that the PFP suffix tree can be efficiently constructed for very large repetitive datasets and that its operations perform competitively with other compressed suffix trees that can only handle much smaller datasets.

The paper deals with an approximate string matching in CRISPR/Cas9 design tools. The approximate string matching is transformed into sequence of exact string matching tasks processed by fast succinct (compressed) self-index. The number of the tasks is rapidly decreased by filtering technique based on de Bruijn graph.

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.

In this article, we propose a novel pattern matching algorithm, called BAPM, that performs searching in the encoded genomic sequences. The algorithm works at the level of single bytes and it achieves sublinear performance on average. The preprocessing phase of the algorithm is linear with respect to the size of the searched pattern m. A simple O(m)-space data structure is used to store all factors (with a defined length) of the searched pattern. These factors are later searched during the searching phase which ensures sublinear time on average. Our algorithm significantly overcomes the state-of-the-art pattern matching algorithms in the locate time on middle and long patterns. Furthermore, it is able to cooperate very easily with the block q-gram inverted index. The block q-gram inverted index together with our pattern matching algorithm achieve superior results in terms of locate time to the current index data structures for less frequent patterns. We present experimental results using real genomic data. These results prove efficiency of our algorithm.

Summary More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naïve algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols, and the increasing order of their probabilities in the text was the best.

Práce se zaměřuje na přibližné vyhledávání s nejvýše k chybami. Chyby jsou definovány s využitím Levenshteinovy vzdálenosti. Pro řešení této úlohy jsem navrhl filtrační algoritmus založený na pigeonhole principu. Prohledávaný text se předpokládá velký, implementovaný algoritmus proto používá FM-Index. Program je na poli vyhledávání v DNA srovnán s nástrojem BLAST. Experimenty ukázaly, že v některých aspektech je má implementace lepší.

Summary form only given. We address the problem of positional indexing in natural language domain. The positional inverted index contains the information of the word positions. Thus, it is able to recover the original textfile, which implies that it is not necessary to store the originalfile. Our Positional Inverted Self-Index (PISI) stores the word position gaps encoded by variable byte code. The inverted lists of single terms are combined into one inverted list that represents a backbone of the text file since it stores the sequence of the indexed words of the original file. The inverted list is synchronized with presentation layer that stores separators, stopwords, as well as variants of the indexed words. The Huffman coding is used to encode the presentation layer. Our experiments prove that PISI is not far from standard positional inverted index in terms of search speed and, at the same time, it is more effective in memory consumption. PISI also proved that it is significantly faster than its close competitor FWCSA in terms of search speed at the same level of memory consumption.PISI naturally undergoes all usual procedures during the construction phase.The indexed text is case folded (all letters are reduced to lower case), stopped(so-called stopwords are omitted) and stemmed (all words are reduced to theirstems using Porter stemming algorithm). PISI uses its presentation layer (proposed by Farina et al. [1]) to store the information lost during the aforementioned procedures. The presentation layer contains one (possibly empty) slot for every word of the inverted list. The slot is composed of the Huffman codes of all non-alphanumeric words and all stopwords preceding the corresponding indexed word. We compared three different indexes in the experimental part: our PISI, word-based self-index FWCSA proposed by Fari~na et al. in [1] and standard positional inverted index II. The fastest instance of PISI with achieved compression ratio 42:91 % proved to be 23 times slower than II (with snippet time 2:37108 second per extracted character for 1 000 extracted words). Furthermore, PISI proved to achieve usually an order of magnitude better snippet time at some level of compression ratio in comparison to FWCSA. E.g. PISI with compression ratio 42:91 % achieves snippet time 3:84108 second per extracted character for 10 extracted words. On the other hand, FWCSA with compression ratio 42:85 % achieves snippet time 1:25 106 second per extracted character for 10 extracted words. Finally, PISI is able to achieve the best compression ratio among of all tested algorithms, which is 39:73 %.

Current compression solutions either use a limited size locality-based context or the entire input, to which the compressors adapt. This results in suboptimal compression effectiveness due to missing similarities further apart in the former case, or due to too generic adaptation. There are many deduplication and near deduplication systems that search for similarity across the entire input. Although most of these systems excel with their simplicity and speed, none of those goes deeper in terms of full-scale redundancy removal. We propose a novel compression and archival system called ICBCS. Our system goes beyond standard measures for similarity detection, using extended similarity hash and incremental clustering techniques to determine groups of sufficiently similar chunks designated for compression. ICBCS outperforms conventional file compression solutions on datasets consisting of at least mildly redundant files. It also shows that selective application of weak compressor results in better compression ratio and speed than conventional application of a strong compressor.

An algorithm for very efficient compression of a set of natural language text files is presented. Not only a very good compression ratio is reached, the used compression method allows fast pattern matching in compressed text, which is an attractive property especially for search engines. Much information is stored in the form of a large collection of text files. The web search engines can store the web pages in the raw text form to build so-called snippets or to perform so-called positional ranking functions on them. Furthermore, there exist many other similar contexts such as the storage of emails, application logs or the databases of text files (literary works or technical reports). In this paper, we address the problem of the compression of a large collection of text files distributed in cluster of computers, where the single files need to be randomly accessed in very short time. The compression algorithm is based on a word-based approach and the idea of combination of two statistical models: global model (common for all the files of the set) and local model. The latter is built as a set of changes that transform the global model to the proper model of the single compressed file.

Nowadays, decreasing cost and better accessibility of sequencing methods have enabled studies of genetic variation between individuals of the same species and also between two related species. This has led to a rapid increase in biological data consisting of sequences that are very similar to each other, these sequences usually being stored together in one database. We propose a compression method based on Wavelet Tree FM-index optimized for compression of a set of similar biological sequences. The compression method is based on tracking single changes (together with their context) between every single sequence and the chosen reference sequence. We call our compression method BIO-FMI. The space complexity of our self-index is O(n+n log σ+N+N log σ+N' (logr+logN'/r) + N'+N' log n+r log N'+r log N) bits when applied on a set of r sequences, where n is the length of the reference sequence, N is the total length of distinct segments in all sequences, N' is the count of distinct segments in all sequences and σ is the size of the alphabet. BIO-FMI distinguishes so-called primary occurrences (occurring in the reference sequence) and secondary occurrences (not occurring in the reference sequence). BIO-FMI can locate each primary occurrence in O(s log σ + r log N'/r) time and each secondary occurrence in O(s log σ), where s is the length of a sample with a localization pointer. BIO-FMI gives very promising results in compression ratio and in locate time when performed on an extremely repetitive data set (less than 0.5% mutations) and when the searched patterns are of smaller lengths (less than 20 bases). BIO-FMI is competitive in extraction speed and it seems to be superior in time needed to build the index, especially in the case when the alignments of single sequences are given in advance.

Summary form only given. The web search engines store the web pages in the raw text form to build so called snippets (short text surrounding the searched pattern) or to perform so called positional ranking functions. We address the problem of the compression of a large collection of text files distributed in cluster of computers, where the single files need to be randomly accessed in very short time. The compression algorithm Set-of-Files Semi-Adaptive Two Byte Dense Code (SF-STBDC) is based on the word-based approach and the idea of combination of two statistical models: the global model (common for all the files of the set) and the local model. The latter is built as the set of changes which transform the global model to the proper model of the single compressed file. Except very good compression ratio the compression method allows fast searching on the compressed text, which is an attractive property especially for search engines property especially for search engines. Exactly the same problem (compression of a set of files using byte codes) was first stated in. Our algorithm SF-STBDC overcomes the algorithm based on (s,c) - Dense Code in compression ratio and at the same time it keeps a very good searching and decompression speed. The key idea to achieve this result is a usage of Semi-Adaptive Two Byte Dense Code which provides more effective coding of small portions ofof the text and still allows exact setting of the number of stoppers and continuers.

Designers of new compression algorithms have to compare their algorithms with the existing ones. They can test over one of standard corpora and compare the achieved compression ratio with published compression ratios made on the same corpus. The corpora are static collections of files so they get older and do not contain new file types that appear. Moreover one can compare only the compression ratio. The times of compression and decompression are very important as well but harder to compare (get the implementation, adjust for the system, run the tests on the same machine).

The paper address the problem of block-oriented natural language compression. Adaptive and semi-adaptive compression methods are nowadays very common in natural language compression field, each of them with different application possibilities. The block-oriented compression is semi-adaptive in terms of one block but it is adaptive in terms of whole input. Our block-oriented compression method is based on the Dense Code idea. It achieves very good compression ratio around 32 % on natural language text and proved to be very fast in searching on the compressed text. We show that our method has some interesting properties which could be applied on digital libraries. The compression method allows direct searching on compressed text. Moreover the vocabulary can be used as a block index which makes some kinds of searching very fast. Another property is that the compressor can send single blocks with correspond ing vocabulary which is considerate to limited bandwidth. In addition the compressed file can be continuously extended without need of previous decompression.Our block-oriented compression method is called Semi-adaptive Two Byte Dense Code (STBDC) and it is a semi-adaptive version TBDC proposed. The STBDC codeword is composed of one or two bytes. The values of the first byte are so-called stoppers or continuers. In the second byte any combination of the bits is allowed which is the point of the limited coding space. The decomposition of the input text into the blocks is based on the limit of the coding space. The end of block must always come when the coding space given by the number of stoppers is exhausted. The changes between the following blocks are encoded in the dictionary file so the the original dictionary for the corresponding block can be easily and quickly reconstructed.

The constant advances in sequencing technology have redefined the way genome sequencing is performed. They are able to produce tens of millions of short sequences (reads), during a single experiment, and with a much lower cost than previously possible. Due to this massive amount of data, efficient algorithms for mapping these reads to reference sequences are in great demand, and recently, there has been ample work for publishing such algorithms. In this paper, we study a different version of this problem: mapping these reads to a dynamically changing genomic sequence. We propose a new practical algorithm, which employs a suitable data structure that takes into account potential dynamic effects (replacements, insertions, deletions) on the genomic sequence. The presented experimental results demonstrate that the proposed approach can be applied to address the problem of mapping millions of reads to multiple genomic sequences.

We develop bit-parallel algorithms for exact string matching.Our algorithms are variations of the BNDM and Shift-Or algorithms.At each alignment the algorithms read a q-gram before testing the state variable.In addition we apply reading a 2-gram in one instruction.Our experiments show that many of the new variations are substantially faster than any previous string matching algorithm on x86 processors for English and DNA data.

DCA (Data Compression using Antidictionaries) is a novel lossless data compression method working on bit streams presented by Crochemore et al. DCA takes advantage of words that do not occur as factors in the text, i.e. that are forbidden. Due to these forbidden words (antiwords), some symbols in the text can be predicted. We build the antidictionary using suffix array in time O(k * N log N), where k is maximal antiword length. Length of suffix array and LCP constructed over the binary alphabet will be 8 times length of the input text. Still memory requirements for suffix array and LCP construction depend only on the length N of input text with O(N), instead of suffix trie with exponential complexity.