12 - Genome compression

Summary

A pragmatic problem arising in the analysis of biological sequences is that collections of genomes and especially read sets consisting of material from many species (see Chapter 16) occupy too much space. We shall now consider how to efficiently compress such collections. Observe that we have already considered in Section 10.7.1 how to support pattern searches on top of such compressed genome collections. Another motivation for genome compression comes from the compression distance measures in Section 11.2.5.

We shall explore the powerful Lempel–Ziv compression scheme, which is especially good for repetitive genome collections, but is also competitive as a general compressor: popular compressors use variants of this scheme.

In the Lempel–Ziv parsing problem we are given a text T = t₁t₂ … t_n and our goal is to obtain a partitioning T = T¹T² … T^p such that, for all i ∈ [1..p], Tⁱ is the longest prefix of which has an occurrence starting somewhere in T¹ … Tⁱ⁻¹. Such strings Tⁱ are called phrases of T. Let us denote by L_i the starting position of one of those occurrences (an occurrence of Tⁱ in T starting somewhere in T¹ … Tⁱ⁻¹). In order to avoid the special case induced by the first occurrences of characters, we assume that the text is prefixed by a virtual string of length at most σ that contains all the characters that will appear in T. Then the string T can be encoded by storing the p pairs of integers (|T¹|, L₁), (|T²|, L₂),…,(|T^p|, L_p). A naive encoding would use 2p log n bits of space. Decoding the string T can easily be done in time O(n), since, for every i, L_i points to a previously decoded position of the string, so recovering Tⁱ is done just by copying the |Tⁱ| characters starting from that previous position.