Statistics for large k-mers with low counts Suppose I have a big genome and a small one (ex. mitochondrion) And I would like to know which words or k-mers of length k (ex. "AGCCGTA" - k = 7) are under/over-represented in both genomes, but I know when using a high Markov model (Rocha et al. it led to a powerless statistic tests and difficulties to find real under/over-represented kmers (False positive results), because of low counts when using bigger k lengths. Any of you friends have a suggestion of a different or robust model (even statistic test) to access this comparison?
Thanks in advance. Paulo
PS - I tried this question in Biostars to, but unfortunately no suggestions.
 A: With four bases (A,C,G,T) possible at each location, there are $4^7=16384$ potential 7-mers in DNA.  The human mitochondrial genome is a circle of double-stranded DNA 16,568 base-pairs* in length. The circle thus has 16,568 potential starting locations for a 7-mer on each strand. One might expect approximately 1 of each 7-mer on each strand if all were random.
The four bases are not represented equally on single strands of that genome, however. On the "L-strand" of the DNA there are 5124 A, 5181 C, 4094 T, and 2169 G. The complementary "H-strand" is described in the reverse order, with complementary base replacements (A->T, C->G, G->C, T->A). Evaluation of over-representation thus must be strand-specific.
There might be a clever combinatorial solution to this problem, but repeated samples of size 16,568 without replacement from a set of 5124 A, 5181 C, 4094 T, and 2169 G can provide an empirical null distribution for the L-strand sequence. A few thousand samples might be enough, depending on the precision you want. For evaluating matches with a k-mer, add the first (k-1) bases to the end of each sample to account for the circular structure of the genome.
The way to apply that null distribution depends on how you choose the k-mers. If there's a particular k-mer that you have in mind that wasn't chosen based on your knowledge of the mitochondrial genome, you can just see how frequently that k-mer matches the simulations in your few thousand null-distribution samples. That might also be OK for evaluating, in the mitochondrial genome, the specific k-mers found to be over-represented by other methods in the larger genome, but I haven't thought that through carefully.
If you are choosing the k-mer based on its known high prevalence in the mitochondrial genome or if you are evaluating all k-mers, then you need to evaluate how frequently any k-mer appears that frequently among your null-distribution samples.

*Although the reference sequence shows 16,569 bases, one of those bases represents an erroneous duplication of a "C" base in the L-strand at positions 3106-3107 in early sequencing work. As many studies had relied on that numbering before the error was found, position 3107 is now reported as "N" to maintain the historical record of base numbering. See the annotations of the NCBI Reference Sequence. The "L-strand" is reported by NCBI. I downloaded the sequence from this page.
