Discovering related DNA sequences via mutual information

摘要

One of the problems in DNA and protein sequence comparisons is to decide whether the observed similarity should be explained by their relatedness or by the mere presence of some shared internal structure, e.g., shared internal repetitive patterns. Machine discovery of related DNA sequences critically depends on a solution to this problem. In this paper we propose a general solution that is based on minimal length encoding: we measure mutual information between two sequences as the difference between the encoding length of one of the sequences sequence and its encoding length relative to the other sequence; two sequences are considered similar if the mutual information exceeds a threshold of significance; the significance is determined using an extension of the newly proposed algorithmic significance method. We show that mutual information factors out sequence similarity that is due to shared internal structure and thus enables discovery of truly related sequences. In addition to this general method, we also propose an efficient way to compare sequences based on their subword composition that does not require any a priori assumptions about k-tuple length.