Self-indexes are data structures that simultaneously provide fast search of and access to compressed text and are promising for genomic data but in their usual form are not able to exploit the high level of replication present in a collection of related genomes. Our RLZ approach is to store a self-index for a base sequence and then compress every other sequence as an LZ77 encoding relative to the base. For a collection of r sequences totaling N bases, with a total of s point mutations from a base sequence of length n, this representation requires just nH_k(T)+slogn+slog(N/s)+O(s) bits. At the cost of negligible extra space, access to consecutive l symbols requires O(l+logn) time. Our experiments show that, for example, RLZ can represent individual hu- man genomes in around 0.1 bits per base while supporting rapid access and using relatively little memory.

Software

The source for the RLZ compression and decompression algorithms. Note that the source for random access (display()) is not included.

Version 0.1.1

March 1, 2011

• RLZ compression
• Change log

Version 0.1

February 27, 2011

• RLZ compression

Data

• Yeast (cere_assemblies.tgz and para_assemblies.tgz)
• Human reference genome (hs_ref_GRC37_chr*.fa.gz)
• Craig Venter genome (hs_alt_HuRef_chr*.fa.gz)
• Korean genome
• Chinese genome

Publications

• S. Kuruppu, S. J. Puglisi and J. Zobel, Optimized Relative Lempel-Ziv Compression of Genomes, ACSC2011, 2011.
• S. Kuruppu, S. J. Puglisi and J. Zobel, Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval, SPIRE2010, 2010

Contact

Please direct any queries regarding this research and the software to Shanika on kuruppu [at] csse [dot] unimelb [dot] edu [dot] au