Introduction

We consider the problem of compressing a set of substrings sampled from a string. In particular, given a string 𝑋 of length 𝑛 and two integer parameters 𝑑 and 𝑚, 𝑚 ≥ 2𝑑, we call a sample of 𝑋 a substring of 𝑋 of length 𝑚 starting at any position 1 + 𝑖 • 𝑑 in 𝑋, where 𝑖 ≥ 0. We refer to the samples as 𝑆 𝑖 = 𝑋[(𝑖 − 1) • 𝑑 + 1..(𝑖 − 1) • 𝑑 + 𝑚], for 𝑖 ≥ 1, and to the concatenation as 𝑆 = 𝑆 1 𝑆 2 • • • 𝑆 𝑟 , where 𝑟 = ⌊(𝑛 − 𝑚)/𝑑⌋ + 1. Note that if 𝑛−𝑚 𝑑 is not an integer, then the final few characters of 𝑋 will not be part of any sample.

If 𝑋 is viewed as a genome sequence, the above substring sampling process corresponds to an idealized model of short read DNA sequencing. In the language of genome sequencing, 𝑚 is the read length and 𝑚/𝑑 is the so-called coverage (the number of samples that cover a given position in 𝑋, on average). Our assumption that 𝑚 ≥ 2𝑑 corresponds to a coverage of at least 2, which is the relevant case for DNA sequencing. 𝑆 represents a file of short read sequences -the typical output of a sequencing experiment. Our sampling process idealizes short read sequencing in at least two ways. Firstly, short read sequencing may produce strings of slightly different length and may introduce errors -insertions, deletions, and substitutions of lettersto the sampled strings, albeit with fairly low probability for present-day short read technology (𝑝 < 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. [1]).

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 • 10 9 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 size 1 , 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., [2,3,4,5]). None are yet in wide use. However, to our knowledge, no careful analysis of the compressibility of short read data sets-even in an idealized setting such as that described above-has been undertaken. This article addresses that need. In particular, we derive a non-trivial upper bound on the size of the LZ parsing [6,7] of 𝑆, the concatenation of sampled substrings, in terms of 𝑛, 𝑚, 𝑑 and the size of the LZ parsing of 𝑋. We also show a different upper bound that holds regardless of the order in which the samples are concatenated to form 𝑆.

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. Thus, the LZ factorization of our example string 𝑋 = zzzzzipzip produces the following 𝑧 𝑋 = 5 factors, 𝑓 1 = z, 𝑓 2 = zzzz, 𝑓 3 = i, 𝑓 4 = p, 𝑓 5 = zip.

Preliminaries

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.

𝑍 = 𝑛 − (𝜎/(𝜎 − 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 [8].

We close this section with another well-known property of the LZ parsing we make use of in the proof of our main theorem.

Upper Bound on the Number of LZ Phrases of the Concatenation of Samples

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 𝑆 = 𝑆 1 𝑆 2 • • • 𝑆 𝑟 , where 𝑟 = ⌊(𝑛 − 𝑚)/𝑑⌋ + 1, and, for 𝑖 ∈ [1..𝑟], 𝑆 𝑖 = 𝑋[(𝑖 − 1) • 𝑑 + 1..(𝑖 − 1) • 𝑑 + 𝑚].

Let us write, for 𝑖 ≥ 1, 𝑆 𝑖 = 𝑣 𝑖 𝑥 𝑖 , where |𝑣 𝑖 | = 𝑚 − 𝑑 and |𝑥 𝑖 | = 𝑑. Then 𝑋 and 𝑆 can be written as follows, where |𝑢| < 𝑑:

𝑋 = 𝑣 1 𝑥 1 𝑥 2 • • • 𝑥 𝑟 𝑢,(1)𝑆 = 𝑣 1 𝑥 1 𝑣 2 𝑥 2 𝑣 3 𝑥 3 • • • 𝑣 𝑟 𝑥 𝑟 .(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). Definition 2. 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 𝑃 𝑟𝑜𝑗 𝑆 ([𝑏, 𝑒]) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ( ⋃︀ 𝑗 𝜄=𝑖 [𝜄𝑚 − 𝑑, 𝜄𝑚]) ∪ [(𝑖 − 2) • (𝑚 − 𝑑) + 𝑏, (𝑖 − 1)𝑚]∪ [𝑚𝑗 + 𝑚 − 𝑑 + 1, 𝑗(𝑚 − 𝑑) + 𝑒] if 𝑚 − 𝑑 < 𝑏 [𝑏, 𝑒] if 𝑏, 𝑒 ≤ 𝑚 − 𝑑 [𝑏, 𝑚 − 𝑑] ∪ 𝑃 𝑟𝑜𝑗 𝑆 [𝑚 − 𝑑 + 1, 𝑒] 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 . . . 𝑥 𝑟 . . . 𝑆 = . . . . . . . . . . . . . . . 𝑋[𝑏, 𝑒] = 𝑃 𝑟𝑜𝑗 𝑆 ([𝑏, 𝑒]) = 𝑣 𝑖−1 𝑥 𝑖 𝑥 𝑖−1 𝑣 𝜄 𝑥 𝜄 𝑣 𝑗 𝑥 𝑗 𝑣 𝑗+1 𝑥 𝑗+1 𝑣 𝑖Proof. Let ℓ = |𝑓 |, 𝑘 = ⌈ ℓ 𝑑 ⌉ and 𝑓 = 𝑋[𝑠..𝑠 + ℓ − 1] = 𝑥 ′ 𝑥 𝑖 𝑥 𝑖+1 • • • 𝑥 𝑗 𝑥 ′′

, where 𝑥 ′ and 𝑥 ′′ are a proper suffix 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 suffix 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 suffix 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 suffix 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. In particular, a phrase 𝑓 and its corresponding source 𝑓 ′ in 𝑋 are represented with distinct colors for each of the 𝑥 𝑖 segments of 𝑋 intersected by the phrase. Finally, the projection 𝑃 𝑟𝑜𝑗 𝑆 (𝑓 ′ ) of the source is shown. It is clear from the figure that, in 𝑆 ′ , the samples intersecting some string in the projection of 𝑓 ′ fully contain at least one substring of the projection of 𝑓 .

𝑋 = 𝑣 1 𝑥 1 𝑓 ′ = 𝑋[𝑏, 𝑒] 𝑥 𝑗−1 𝑥 𝑗 𝑥 𝑗+1 𝑥 𝑗+2 . . . 𝑓 𝑥 𝑖−1 𝑥 𝑖 𝑥 𝑖+1 𝑥 𝑖+2 . . . 𝑥 𝑟 𝑢 . . . 𝑆 = 𝑣 1 𝑥 1 𝑥 𝑗−1 𝑃 𝑟𝑜𝑗 𝑆 ([𝑏, 𝑒]) . . . 𝑣 𝑗 𝑥 𝑗 𝑣 𝑗+1 𝑥 𝑗+1 𝑣 𝑗+2 𝑥 𝑗+2 . . . 𝑥 𝑗−1 |𝑆 𝑗 | ≥ 2|𝑥 𝑗 |

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

Upper Bound for Arbitrary Concatenation Order

This section examines the effect 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 suffix 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 suffix 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 Summing over all samples 𝑆 𝑖 , we thus get

𝑧 𝑆 ′ ≤ 𝑟 ∑︁ 𝑖=1 (2 + |𝑢 𝑖 |) = 2𝑟 + 𝑟 ∑︁ 𝑖=1 |𝑢 𝑖 | = 2𝑟 + 𝑛,

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.

Experimental Results

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

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 [9] of length 29 836, that is factorized in 4 373 LZ phrases. We also performed experiments on extreme cases between which real-life genomes lie: Fibonacci words and random words. 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.

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 [8], see Theorem 1.

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 different 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 [8] by Kärkkäinen (rounded points), when repetitive strings are considered, our bound is not worse than the existing one for the string order concatenation, while it gets more loose with the concatenation in arbitrary order. See the plots for Fibonacci words and the concatenation of 50 genomes of SARS-CoV-2. On the other hand, for non repetitive strings, namely random strings and the single viral genome in the plots, the existing bound is often better than ours. A summary of relevant results for the Fibonacci word and the single SARS-CoV2 genome. For each sampling frequency 𝑑, we report the value of 𝑚 for which the maximum number of phrases in the concatenation of the samples is produced in both string order and after the random shuffling. We further show the counts and the value of our bound for the mentioned 𝑚.

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.

Concluding Remarks

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 𝑆 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