On Compressing Collections of Substring Samples

Given a string X = X[1..n] of length n, and integers m and d, such that n > m >= 2d > 0, we consider the problem of compressing the string S formed by concatenating the substrings of X of length m starting at positions i congruent 1 mod d. In particular, we provide an upper bound of (2n-m)/d + 2z + (m - d) on the size of the Lempel-Ziv (LZ77) parsing of S, where z is the size of the parsing of X. We also show that a related bound holds regardless of the order in which the substrings are concatenated in the formation of S. If X is viewed as a genome sequence, the above substring sampling process corresponds to an idealized model of short read DNA sequencing.