RLZAP: relative Lempel-Ziv with adaptive pointers

DOI10.1007/978-3-319-46049-9_1MaRDI QIDQ1796822zbMATH OpenOpenAlexFDO

Authors Anthony J. Cox, Andrea Farruggia, Travis Gagie, Simon J. Puglisi, Jouni Sirén

Publication date 17 October 2018

Full work available at URL https://arxiv.org/abs/1605.04421

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: Relative Lempel-Ziv (RLZ) is a popular algorithm for compressing databases of genomes from individuals of the same species when fast random access is desired. With Kuruppu et al.'s (SPIRE 2010) original implementation, a reference genome is selected and then the other genomes are greedily parsed into phrases exactly matching substrings of the reference. Deorowicz and Grabowski (Bioinformatics, 2011) pointed out that letting each phrase end with a mismatch character usually gives better compression because many of the differences between individuals' genomes are single-nucleotide substitutions. Ferrada et al. (SPIRE 2014) then pointed out that also using relative pointers and run-length compressing them usually gives even better compression. In this paper we generalize Ferrada et al.'s idea to handle well also short insertions, deletions and multi-character substitutions. We show experimentally that our generalization achieves better compression than Ferrada et al.'s implementation with comparable random-access times.

Recommendations

• Relative Lempel-Ziv with constant-time random access
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• Lempel-Ziv-like parsing in small space
• Relative Lempel-Ziv Compression of Suffix Arrays
• Fast relative Lempel-Ziv self-index for similar sequences

Cited in

(4)

• Relative Lempel-Ziv with constant-time random access
• Online LZ77 parsing and matching statistics with RLBWTs
• Refining the \(r\)-index
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval

This page was built for publication: RLZAP: relative Lempel-Ziv with adaptive pointers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1796822)