Sequence Similarity by Gapped LZW
Alberto Apostolico, Fabio Cunial · 2011
Measures of sequence similarity based on some underlying notion of relative compressibility are becoming increasingly of interest in connection with massive tasks of textfile classification such as, notably, in document classification and molecular taxonomy on a genomic scale. Sequences that are similar can be expected to share a large number of common substrings, whence some successful measures in this class have been based on the substring composition of the input sequences. Among the corresponding methods, one finds suitable extensions of the bag-of-words together with more explicit resorts to data compression techniques such as LZ77. The approach presented in this paper explores the potential of LZW - the variant of LZ78 proposed by Welch -- as well as of some of its lossy variants, in this context. Whereas LZW has a faster and simpler implementation than LZ77, the vocabulary underlying LZW is significantly smaller than that of LZ77. In addition, recently introduced "gapped" variants of LZW are considered that are equally straightforward to implement but allow for a controlled number of don't cares to be introduced in the substrings that constitute the dictionary used in compression. This study assesses the robustness of compressibility based measures of similarity under these faster yet inherently more dispersive paradigms built around LZW.