Compression of Biological Sequences by Greedy Off-line Textual Substitution

In bio-sequence repositories and other applications, like for instance in the production of a Cd-rom or magnetic disk for massive data dissemination, one could afford the extra cost of performing compression off-line in exchange for some gain in compression. In view of the intractability of optimal off-line macro schemes various approximate schemes have been considered.Here we follow one of the simplest possible steepest descent paradigms. This will consist of performing repeated stages in each one of which we identify a sub-string of the current version of the text yielding the maximum compression, and then replace all those occurrences except one with a pair of pointers to the untouched occurrence. This is somewhat dual with respect to the bottom up vocabulary buildup scheme considered by Rubin. This simple scheme already poses some interesting algorithmic problems.In terms of performance, the method does outperform current Lempel-Ziv implementations in most of the cases. Here we show that, on biological sequences, it beats all other generic compression methods and approaches the performance of methods specifically built around some peculiar regularities of DNA sequences, such as tandem repeats and palindromes, that are neither distinguished nor treated selectively here.The most interesting performances, however, are obtained in the compression of entire groups of genetic sequences forming families with similar characteristics. This is becoming a standard and useful way to group sequences in a growing number of important specialized databases. On such inputs, the approach presented here yields scores that are not only better than those of any other method, but also improve increasingly with increasing input size. This is to be attributed to a certain ability to capture distant relationships among the sequences in a family, a feature the merits of which were dramatically exposed in the recent paper [4].