Alignment-Free Sequence Comparison (I): Statistics and Power

Large-scale comparison of the similarities between two biological sequences is a major issue in computational biology; a fast method, the D-2 statistic, relies on the comparison of the k-tuple content for both sequences. Although it has been known for some years that the D-2 statistic is not suitable for this task, as it tends to be dominated by single-sequence noise, to date no suitable adjustments have been proposed. In this article, we suggest two new variants of the D-2 word count statistic, which we call D-2(S) and D-2*. For D-2(S), which is a self-standardized statistic, we show that the statistic is asymptotically normally distributed, when sequence lengths tend to infinity, and not dominated by the noise in the individual sequences. The second statistic, D-2*, outperforms D-2(S) in terms of power for detecting the relatedness between the two sequences in our examples; but although it is straightforward to simulate from the asymptotic distribution of D-2*, we cannot provide a closed form for power calculations.