Genomic Compression with Decoder Alignment under Single Deletion and Multiple Substitutions

We address the problem of compressing genomic read data produced by modern shotgun sequencing technologies, where a reference genome, closely similar to the sequenced one, is available only at the decoder. This problem, addressed by distributed source coding techniques, requires an alignment and validation layer in the decoder. In this work, we extend a previous work, to allow a single deletion along with the previously addressed multiple substitutions. The results include a new distance for efficient alignment under deletion and substitutions, a derivation of the exact distribution of this distance on random sequences, as well as procedures to recover the read from multiple invocations of a substitutions-only decoder.