Compression-based normal similarity measures for DNA sequences

Similarity measures based on compression assess the distance between two objects based on the number of bits needed to describe one, given a description of the other. Theoretically, compression-based similarity depends on the concept of Kol-mogorov complexity, which is non-computable. The implementations require compression algorithms that are approximately normal. The approach has important advantages (no signal features to identify and extract, for example) but the compression method must be normal. This paper proposes normal algorithms based on mixtures of finite context models. Normality is attained by combining two new ideas: the use of least-recently-used caching in the context models, to allow deeper contexts, and data interleaving, to better explore that cache. Examples for DNA sequences are given (at the human genome scale).

1. INTRODUCTION

Measuring the similarity between two numeric signals or images or between two symbolic signals such as DNA sequences is an important problem. For numeric signals, the simplest approach is to fix a norm and measure the size of the difference of two signals using that norm, . In this context, the -norm is probably the one most often used. This approach works reasonably well when, for example, one signal is a noisy version of the other. Under more general circumstances, the direct application of a norm may yield meaningless results (imagine that one signal is a scaled version of the other, for example). Using norms in this way is of course also out of the question for symbolic sequences (in which the concept of “difference” is not even defined).