Algorithmic significance, mutual information, and DNA sequence comparisons

摘要

The newly proposed algorithmic significance method (6) enables recognition of patterns in DNA sequences at prespecified significance levels via minimal length encoding. We extend the method to provide a formal framework for DNA sequence comparisons via mutual information. While in this paper we restrict our discussion to DNA sequence analysis, the methods that are presented are potentially applicable in many other domains. Under a few simplifying assumptions, we show that significance of sequence similarity depends exponentially on mutual information. In addition to this estimate of significance, the concept of mutual information provides solutions to the following two problems in DNA sequence comparisons: Factoring out contribution of shared repetitive patterns and factoring out bias due to partial sequencing.