EE5390 Course Information

Genomes of two individuals of the same species are highly related. These are perhaps not well modeled by standard distributions, since one DNA sequence can be obtained by performing a small number of edit operations (insertion, deletion, transposition) on another. Traditional compression algorithms don't do a very good job of compressing large collections of DNA sequences.

• Deorowicz et al, "Genome compression: a novel approach for large collections," Bioinformatics
• Deorowicz et al, "GDC2: Compression of large collections of genomes," Scientific reports

Finding the DNA sequence of an individual is a very interesting process in itself. The most popular technique for sequencing (estimating the DNA sequence) is called shotgun sequencing. This yields short subsequences of the actual DNA sequence (with errors). These, and the quality scores (a score measuring how reliable the read is) are stored in a format called FASTQ. Compressing such files is of great interest.

• Deorowicz and Grabowski, "Compression of DNA sequence reads in FASTQ format," Bioinformatics
• Ochoa et al, "QualComp: a new lossy compressor for quality scores based on rate distortion theory," BMC Bioinformatics
• Chandak et al, "SPRING: a next-generation compressor for FASTQ data"

How easy is it to reconstruct an unknown string if we are only given short substrings of it (without mentioning which locations they are taken from)? This is called the trace reconstruction problem, and is a fascinating topic closely related to the problem of reconstructing DNA from shotgun reads.

• Batu et al, "Reconstructing a string from random traces," SODA 2004
• Acharya et al, "String reconstruction from its substring compositions," https://arxiv.org/pdf/1403.2439.pdf

This is also closely related to the above problems, but also occurs in cloud synchronization. If we have two files, one of which is an updated version of the other (and hence highly correlated), then how do we compress this jointly? In particular, if the second file is obtained by randomly inserting/deleting text from the first, then what is the minimum rate of compression of the second file given that both the compressor and decompressor have access to the first?

• Wang et al, "File updates under random/arbitrary insertions and deletions," https://arxiv.org/pdf/1502.07830.pdf

This is optimized for compression and decompression speed. See https://facebook.github.io/zstd for more details. The exact values of the parameters are not important to study here. What you need to focus on are the basic concepts, what the building blocks of the algorithm are, etc.

MPEG-G is a new set of standards for storage and compression of sequencing data

• https://mpeg-g.org/documents/

What if the source is not a sequence but has a different structure, such as a graph? This arises in instances such as compression of the details of users of a social network, where we can consider each user as a vertex, and two users are connected if they are "friends."

• Mohri et al, "Automata and graph compression" https://arxiv.org/abs/1502.07288
• Choi and Szpankowski, "Compression of graphical structures: fundamental limits, algorithms and experiments," https://ieeexplore.ieee.org/document/6145505
• Delgosha and Anantharam, "Universal lossless compression of graphical data" IEEE Transactions on Information Theory

In most circumstances we can handle situations where the distribution of the source is unknown. But what happens when the alphabet itself is unknown, and what if the alphabet size could be arbitrarily large? In this scenario, it might not be possible to get a reliable estimate of the input distribution.

• Orlitsky et al, "Universal compression of memoryless sources over unknown alphabets," https://ieeexplore.ieee.org/document/1306545 (this was groundbreaking work and won an IEEE Trans-IT best paper award)
• This paper led to some great ideas, which eventually went into problems of estimation. ICML paper: https://people.ece.cornell.edu/acharya/papers/pml-opt.pdf

Traditional compression algorithms are designed only for storage. Suppose that we have a large database, which we need to compress in order to save space. Suppose that we use gzip, zip, etc. for compression. If we want to query this database, then we have to first decompress, only then can we query the database. Can we design a compression algorithm such that the queries can be made directly on the compressed file?

• Navarro and Makinen, "Compressed full text indexes" https://dl.acm.org/doi/pdf/10.1145/1216370.1216372
• Mazumdar and Pal, "Semisupervised clustering by queries and locally encodable source coding," https://arxiv.org/abs/1904.00507
• Mazumdar et al, "Local recovery in data compression for general sources," ISIT, https://www.rle.mit.edu/sia/wp-content/uploads/2015/07/2015-mazumdar-chandar-wornell-isit.pdf
• Vatedka and Tchamkerten, "Local decode and update for big data compression" https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9115085
• There is an entire area of research called compressed data structures, and books have been written about this. See this or this.

• The context tree weighting method: https://ieeexplore.ieee.org/document/382012
• Compression using the Burrows Wheeler transform
• Distributed source coding using linear codes: see this or this
• Wainwright et al, "Lossy source compression using low density generator matrix codes,"
• Donoho, "Compressed sensing"
• Gray and Neuhoff, "Quantization"
• Neural network compression: this or this
• In-depth description of the algorithms in data compression standards such as JPEG or MPEG