MODULAR DATA COMPRESSION TO OPTIMALLY LOCATE REGULAR SEGMENTS IN SEQUENCES. APPLICATION TO DNA SEQUENCE ANALYSIS

摘要

A new location method for regular segments in sequences is presented. It uses the Minimum Description Length (MDL) criterion. If a lossless compressor achieves size reduction by exploiting a regularity, our algorithm TurboOptLift locates very quickly the segments where the regularity is probably present and those where it is not. The location is optimal from a MDL viewpoint. We apply the method to the problem of locating approximate tandem repeats in DNA sequences.