Given a string = [1..] of length , and integers and , such that > ≥ 2 > 0, we consider the problem of compressing the string formed by concatenating the substrings of of length starting at positions ≡ 1 (mod ). In particular, we provide an upper bound of (2 − )/ + 2 + ( − ) on the size of the Lempel-Ziv (LZ77) parsing of , where is the size of the parsing of . We also show that a related bound holds regardless of the order in which the substrings are concatenated in the formation of . If is viewed as a genome sequence, the above substring sampling process corresponds to an idealized model of short read DNA sequencing.
( < 0.01 for Illumina short reads, for example). Secondly, in short read sequencing, coverage
is not completely uniform, fluctuating across the genome for a variety of reasons (see, e.g. [
The extraordinarily wide adoption of high-throughput sequencing in medical and evolutionary biology over the last decade has made short read data sets abundant. These data sets are also very large. For example, a typical human sequencing experiment might run at 20x coverage on a underlying genome of size = 3 · 109 nucleotides. The resulting read set in FASTQ format (a standard file format, which stores one ASCII-encoded short read sequence per line—akin to our string) is then 60 gigabytes in size. The de facto standard in most labs (and large institutions such as, e.g., the NCBI) is to compress such files with the gzip all-purpose file compressor, which usually leads to a factor four reduction in size1, or 15GB in our human sequencing example. A gzip’d large read set is thus, alas, still relatively large.
With the rapid growth in, and the need to store, short read data sets, specialized compressors
that exploit properties inherent to such data sets will become paramount. Several read set
specific compressors have now been developed (see, e.g., [
In the next section we set notation and basic concepts and results used throughout. In Sections 3 and 4 we establish the above mentioned bounds, and in Section 5 we gauge the tightness of these bounds experimentally. We then sketch several directions for future work.
Throughout we consider a string = [1..] = [
For example, in the string = zzzzzipzip, lcp(2, 5) = 1 = |z|, and lcp(5, 8) = 3 = |zip|. For technical reasons we define lcp (, 0) = lcp(0, ) = 0 for all .
Definition 1 (LZ Factorization). The LZ factorization of is a factorization = 12 . . . of into phrases such that each phrase (a substring of ) is either
1. a letter that does not occur in 1 · · · − 1, or 1This can be loosely interpreted as gzip, a sliding-window dictionary compressor with window size too small to capture any large dispersed repeated substrings present in the file, essentially reducing the space used by each DNA letter from the 8 bits used in the plain ASCII encoding to the 2 bits that a flat minimal binary code for four letters would use.
2. the longest substring that occurs at least twice in 1 · · · .
Thus, the LZ factorization of our example string = zzzzzipzip produces the following = 5 factors, 1 = z, 2 = zzzz, 3 = i, 4 = p, 5 = zip.
We denote with ℓ = || the length of phrase , and with the starting position of phrase in , i.e., = 1 + ∑︀< ℓ . Finally, we denote with the position of the first occurrence of substring in and we call substring [.. + ℓ − 1] the source of . Note that phrases and sources are allowed to overlap, as is the case with 2 in our example.
The following is a known upper bound on the number of phrases in the parsing.
Theorem 1 ([
− (/ ( − 1)) log − log log − (1/( − 1)) .
We will return to the above bound later in the paper, but for now we note that it is
asymptotically tight. In particular, an appropriate prefix of the de Bruijn sequence contains at least
/⌈log ⌉ LZ phrases [
We close this section with another well-known property of the LZ parsing we make use of in the proof of our main theorem.
Fact 1. Let be a string, and 1 < ≤ ≤ | |. If = [..] has an occurrence before , i.e., if there exists an ′ < s.t. [′..′ + || − 1] = , then the interval [, ] can contain at most one starting position of a phrase.
In this section, we show an upper bound on the number of LZ phrases of string formed by concatenating samples from string .
Formally, given a string of length and two integer parameters , , such that ≥ 2, let = 12 · · · , where = ⌊( − )/⌋ + 1, and, for ∈ [1..], = [( − 1) · + 1..( − 1) · + ].
Let us write, for ≥ 1, = , where || = − and || = . Then and can be written as follows, where || < :
= 112 · · · , = 112233 · · · . (1) (2)
We will now count the number of phrases of the LZ parsing of string . Note that this is equivalent to counting the number of starting positions of phrases.
Lemma 1. Let and denote the beginning resp. ending position of the ’s in the factorization of given in (2). Then, for > 1, the interval [, ] can contain at most one starting position of a phrase.
⎪ ⎪ ⎧(⋃︀ ⎪ ⎪ ⎪ ⎪[, ] [, ] = Proof. Since two consecutive samples and +1 overlap by − characters, it follows that, for all > 1, = +1, where is the -length prefix of . Therefore, contains the square for every > 1, and is the start of the second occurrence of in this square. By Fact 1, therefore, [, ] can contain at most one starting position.
Next we will count the number of starting positions in the ’s. For this, we consider phrases of the LZ parsing of , and count how many starting positions these induce in in the worst case. We first need the definition of the projection of a substring of on (see also Figure 1).
Let 1 ≤ ≤ ≤
. We define the projection of substring [, ] on as a collection of substrings in as follows: For , let and denote the starting resp. ending positions of in w.r.t. the factorization given in (1). Then ([, ]) = ⎪⎨[ + − + 1, ( − ) + ]
if − < =[ − , ]) ∪ [( − 2) · ( − ) + , ( − 1)]∪ ⎪⎩[, − ] ∪ [ − + 1, ] if ≤ − < .
if , ≤ −
Informally, a projection in of a substring of is the collections of substrings of coinciding with regions of , namely substrings of which consists of, w.r.t. the factorization given in (1). The first case (see Fig. 1) gives the general situation, when starts after the prefix 1 of , which is covered only by the first sample 1. The second case is when lies fully within 1, while the third case is when starts within 1 and ends after it. = 1 1 . . .
− 1 . . . . . .
+1 . . .
([, ]) = = by [, ] in , and they are all contained in the corresponding ’s in .
Let be a phrase of the LZ parsing of , with starting position and length ℓ. Define ( ) as the number of starting positions in ([, + ℓ − 1]). > − . Then ( ) ≤
|| + 2.
Lemma 2. Let ≥ 2. Let be a phrase of the LZ factorization of , with starting position Proof. Let ℓ = | |, = ⌈ ℓ ⌉ and = [.. + ℓ − 1] = ′+1 · · · ′′, where ′ and ′′ are a proper sufix of
− 1 respectively a proper prefix of +1, both possibly empty. We will show that each of these substrings is charged with at most one phrase starting position. From Fact 1, the claim follows.
By construction of , each of the substrings ′, , +1, . . . , , ′′ will appear contiguously in . The number of these substrings is either or + 1. Additionally, a substring separates the projections in of each pair of contiguous aforementioned substrings of .
Consider now the source ′ of occurring in in some position ′ < . Then [..+ℓ− 1] = [′..′ + ℓ − 1] = ′′ ′+1 · · · ′ ′′, where ′ and ′′ are a proper sufix of ′− 1 respectively a proper prefix of ′+1, both possibly empty. As for , the projection of ′ is also split in in such a way that the projection of each pair of mentioned substrings of ′ is separated by a substring in .
Notice that, since ≥ 2, each in has an occurrence in also as sufix of ′+1, occurring immediately after +1 in . This means that, even if the projections of and ′ in will be split asynchronously, each of the substrings ′, , +1, · · · , , ′′ in the projection of has already occurred as the concatenation of a sufix of some ′ intersecting the projection of ′ and the contiguous ′+1.
There are at most + 1 factors ′, , +1, . . . , , ′′, and each of them has a previous occurrence in . Therefore, by Fact 1, there will be at most + 1 phrase starting positions for . See Fig. 2 for an illustration.
. . . − 1 +1 +2 . . . − 1 +1 +2 . . .
− 1
|| ≥ 2|| +1 +1 +2 +2 . . . = = 1 1 ′ = [, ] 1 1 ([, ])
. . . − 1
Lemma 3. With respect to the factorization of given in (2), the number of phrase starting positions in ’s is at most + 2 .
Proof. The sum of the lengths of all phrases 1, . . . , in the LZ factorization of is the length of the string . Therefore, we can bound the total contribution to of as follows: ∑︁ ( ) ≤ =1 =1 ∑︁( | | + 2) = + 2 .
Theorem 2. Let be the number of phrases of the LZ parsing of , and the number of phrases of the LZ parsing of . Then ≤ 2− + 2 + − .
Proof. We show the maximum number of phrase starting positions in summing up the contribution of the ( − )-length prefix of , and of the remaining ’s (Lemma 3) and ’s (Lemma 1) substrings.
= number of starting positions in 1 + number of starting positions in ’s + number of starting positions in ’s, for ≥ 2 ≤ ( − ) + + 2 + − = 2 − + 2 + − .
Theorem 2 essentially says that the number of LZ phrases of is at most twice the number of samples plus twice the number of LZ phrases of . Note that the important parameter which determines the number of samples is , while influences only the number of samples in which a given position occurs (i.e. / is the so-called coverage).
This section examines the efect that the ordering of the samples in the concatenation has on the number of phrases.
As before, we are given a string of length and two integer parameters and , such that ≥ 2. Let = ⌊( − )/⌋ + 1, and, for ∈ [1..], = [( − 1) · + 1..( − 1) · + ].
We will show that, regardless of the order in which the samples of are concatenated, the number of phrases in the LZ factorization of that concatenation is at most + 2(− ) . We make this argument precise below.
Theorem 3. Let ′ be the concatenation of the samples of in any order, then the number of phrases is ′ ≤ + 2(− ) .
Proof. Fix . We will show that the number of phrase starting positions in sample where it appears in ′ is at most 2 + ||, where is a specific substring of . Let = max{′ < | ′ appears before in ′}, and let be the longest sufix of which is also a prefix of (i.e., is the maximum overlap). Note that may be empty. Similarly, let ′ = min{′ > | ′ appears before in ′}, and let ′ be the longest prefix of ′ which is also a sufix of , again possibly empty. If || + |′| ≥ = ||, then set = . Otherwise, can be written as = ′, for some .
This is a substring of that has not so far been covered by any sample in ′, and this is because of the definition of and ′. We call the new part of ; in particular, if = , then the new part of is empty.
By Fact 1, if is non-empty, then at most one phrase starting position is contained within . Similarly, if ′ is non-empty, at most one starting position is contained within ′. The number of starting positions within the new part can be trivially upper bounded by ||. = − ′ + ... − = = ...
... = ...
... ′ = ...
′
Summing over all samples , we thus get ′ ≤
∑︁(2 + ||) = 2 + ∑︁ || = 2 + , =1 =1 with the last equality using the fact that every position of occurs exactly once in some .
Theorem 3 essentially says that the number of LZ phrases of ′, i.e. of the concatenation of the samples in an arbitrary order, is at most the length of plus twice the number of samples.
In order to gauge the tightness of our bounds, we computed the number of phrases in the conventional LZ factorization (defined in Section 2) of the concatenation of the samples taken from each of the texts in Table 1. We did this for a range of and parameters, and concatenated the samples both in string order and after a random shufling. 5.1. Data Our test data, which contains files of varying repetitiveness is shown in Table 1.
By nature, viruses contain very little recurrent genetic heritage, and so a viral genome
represents a real-world non-repetitive string. We used a genome of SARS-CoV2 taken from
the COVID-19 Data Portal [
taCkoenncfarotemnatthioenCoOfV5I0Dv-i1r9usDgaetnaoPmoertsal [
Word over an alphabet of size 4 built with python function random.choices()
Let 0 = b, 1 = a, the Fibonacci word of order + 1 is the binary word +1 = − 1. In other words, the Fibonacci word of order + 1 is the concatenation of the Fibonacci words of the two previous orders.
By construction, Fibonacci words have a very high degree of repetition, resulting in very few phrases with respect to their length. Random words, on the other hand, could be considered, instead, not repetitive at all. To perform a comparison with the virus genome, we chose a random word of the same length of the genome, and the Fibonacci word of length 28 657, the closest to the length of the genome. The strings are factorized in 4 575 respectively 22 phrases.
We also performed experiments with larger data. In particular, we counted the number of phrases of the concatenation of 50 SARS-CoV2 genomes, which, due to the high similarity of the individual genomes, constitutes a highly repetitive dataset. 5.2. Experiments We are interested in simulating the coverage provided by the most used technologies in genome sequencing. The coverage is given by the number of samples that cover a given position in the text. In the context of genome sequencing, a reasonable coverage is given by large and small , in order to have the coverage as large as possible with reasonable sample lengths.
We perform the experiments on each of the aforementioned texts with = 1, 2, 4, 8, 16, 32, 64, and from 50 to 1 000, in increments of 10. We counted the number of phrases for > .
Figure 4, on top, displays the number of phrases for concatenations of samples in string
order of a Fibonacci word (top-left corner), and of a random string of a similar length (top-right
corner). Below, we show the counts for an arbitrary ordered concatenation of the samples
of the same data. In all figures, the number of phrases for some selected ’s are shown in
distinct colours, in gray for all other ’s. The corresponding coloured line shows our bounds
for each and pair. Finally, the colored rounded points show the existing bound given by
Kärkkäinen [
The analogous comparison is shown in Figure 5 between a single SARS-CoV2 genome and the concatenation of 50 genomes.
The overlapping of the bound lines in all plots reflects the small impact of the sampling length in the bound for fixed .
When the samples are concatenated in string order (on the top of both Figure 4 and 5), the number of phrases in the original string has a big influence on the bound. We can see that the bound lines in the Fibonacci word’s plot are closer to the actual counts than in the other plots, where the number of phrases of the original strings is higher. On the other hand, because of the diferent nature of the bound for the samples in string order versus random order, we can see that the latter bound has a similar trend for the three strings of similar length. In this case, the length and the number of samples of the original string determine the bound rather than its number of phrases.
Comparing the bound given in this paper (lines) to the one reported in Theorem [
max phrases bound
shufled max phrases bound
max phrases bound SARS-CoV2
shufled max phrases bound = 1
In Table 2 we show, for fixed , the maximum number of phrases in , varying . For strings that are already very repetitive (Fibonacci word), the longer the string, the higher the number of phrases. On the other hand, for strings that are not that repetitive (single SARS-CoV2 genome), introducing long repetitions may decrease the number of phrase starting positions in contrast to having a shorter string with very short repetitions. The concatenation of 50 SARS-CoV2 genomes lies in the middle.
(a) Fibonacci word of length 28 657 (b) Random word of length 29 835
This paper has explored the compressibility of collections of substrings sampled from a string. In particular, given a string = [1..] of length with an LZ parsing size of , and integers and , such that > ≥ 2 > 0, we have shown that the size of the LZ parsing of the string (a) SARS-CoV2 genome of length 29 835 (b) Concatenation of 50 SARS-CoV2 genome, of total length 1 490 134 formed by concatenating the substrings of of length starting at positions ≡ 1 (mod ), is bounded by (2 − )/ + 2 + ( − ). We also proved a bound for the case of any arbitrary chosen order of the samples in the concatenation.
There are several avenues future work could take. The most immediate perhaps is the question
of whether the bounds given in Theorem 2 and Theorem 3 can be improved. Another direction
is to derive bounds for other compression measures, such as the size of the smallest context-free
grammar for [
Along the lines of our original motivation from DNA sequencing, how are the bounds afected by the introduction of some probability of error to the sample substrings, such as those errors introduced in collections of strings produced by short-read sequencing technologies?
Finally, note that we have assumed ≤ /2, which corresponds to the interesting case in practice. However, it may be interesting from a theoretical perspective to also examine the case where > /2.