Charging Station: Solving Frequent Words with Mismatches Problem

This lesson uses some notation from Charging Station: The Frequency Array.

To prevent having to generate all 4$^{k}$ k-mers in order to solve the Frequent Words with Mismatches Problem, our goal is to consider only those k-mers that are close to a k-mer in Text, i.e., those with Hamming distance at most d from this k-mer. Given a k-mer Pattern, we, therefore, define its d-neighborhood Neighbors(Pattern, d) as the set of all k-mers that are close to Pattern. For example, Neighbors(ACG, 1) consists of ten 3-mers:

$\space$$\space$$\space$$\space$$\space$ACG $\space$$\space$$\space$$\space$$\space$ CCG $\space$$\space$$\space$$\space$$\space$GCG $\space$$\space$$\space$$\space$$\space$TCG $\space$$\space$$\space$$\space$$\space$AAG $\space$$\space$$\space$$\space$$\space$AGG $\space$$\space$$\space$$\space$$\space$ATG $\space$$\space$$\space$$\space$$\space$ACA $\space$$\space$$\space$$\space$$\space$ACC $\space$$\space$$\space$$\space$$\space$ACT

Exercise Break: Estimate the size of Neighbors(Pattern, d).

Frequency array with up to d mismatches