<p>Let's first establish a lower bound on any solution:</p>
<p>Given a hamming distance <span class="math-container">$D$</span> and an input pattern <span class="math-container">$P$</span> of length <span class="math-container">$N$</span>, there are <span class="math-container">$\sum_{k=0}^D{N \choose k} 3^k$</span> other strings within hamming distance <span class="math-container">$D$</span> of <span class="math-container">$P$</span>. Of course in the worst case, when <span class="math-container">$D=N$</span>, there are <span class="math-container">$4^n$</span> possible strings.
We can also get a closed bound on the number of solutions. We can show that the sum of the first <span class="math-container">$D$</span> binomial coefficients for a fixed <span class="math-container">$N$</span> is bounded by <span class="math-container">${N \choose D} {N-(D-1) \over N-(2D-1)}$</span> as shown <a href="https://mathoverflow.net/a/17236">here</a>. Therefore we have the following closed upper bound on the number of strings within hamming distance <span class="math-container">$D$</span> of some pattern of length <span class="math-container">$N$</span></p>
<p><span class="math-container">$$
\sum_{k=0}^D{N \choose k} 3^k \leq {N \choose D}  {3^D (N-(D-1)) \over N-(2D-1)} \leq \left(\frac{3N}{D}\right)^D {N-(D-1) \over N-(2D-1)}
$$</span></p>
<p>However, for your approach, you are going through recursively, so when the subproblem is on strings within <span class="math-container">$D$</span> of the suffix of length <span class="math-container">$n$</span>, you have <span class="math-container">$\sum_{k=0}^D{n \choose k} 3^k$</span>  of these. Given that you have <span class="math-container">$N$</span> subproblems (suffixes), at first glance it does indeed look like you have roughly <span class="math-container">$\sum_{n=1}^N\sum_{k=0}^D{n \choose k} 3^k$</span> iterations of the innermost for loop. However, in that <code>for</code> loop, you are also computing the Hamming Distance function, which is <span class="math-container">$O(n)$</span>. This means that you have roughly</p>
<p><span class="math-container">$$
\sum_{n=1}^Nn\sum_{k=0}^D{n \choose k} 3^k
$$</span></p>
<p>computations.</p>
<p>I would suggest finding a way to get rid of having to compute the hamming function. Since you are constructing the sequences yourself, you can keep track of each sequences hamming distance from the pattern during construction.</p>

CC BY-SA 4.0
2021-07-01T17:25:40.557Z
Excellent! I missed the complexity for computing Hamming distance. Also, you can correct the first sentence - "Given a hamming distance  D"
Deepak Tatyaji Ahire
CC BY-SA 4.0
2021-07-01T17:27:02.317Z
Thank you very much @Throckmorton.
Deepak Tatyaji Ahire
CC BY-SA 4.0
2021-07-01T16:25:07.613Z
2021-07-01T17:55:24.620Z
2021-07-01T17:55:24.620Z
Throckmorton
<p>I implemented the following <strong>find_neighbors_with_expected_hamming_distance</strong> function that generates all k-mers of Hamming distance at most d from the given Pattern.</p>
<pre><code>from .Hamming_Distance import find_hamming_distance

dp_map_that_stores_all_neighbors_with_expected_hamming_distance = {}

unique_nucleotides = {'A', 'C', 'G', 'T'}


def suffix(pattern):
    if len(pattern) &lt;= 1:
        return None
    else:
        return pattern[1: (len(pattern))]


def first_symbol(pattern):
    if len(pattern) == 0:
        return None
    else:
        return pattern[0]


def find_neighbors_with_expected_hamming_distance(pattern, expected_hamming_distance):
    if expected_hamming_distance == 0:
        return {pattern}

    if len(pattern) == 1:
        return {'A', 'C', 'G', 'T'}

    if (pattern, expected_hamming_distance) in dp_map_that_stores_all_neighbors_with_expected_hamming_distance.keys():
        return dp_map_that_stores_all_neighbors_with_expected_hamming_distance[(pattern, expected_hamming_distance)]

    neighborhood_set = set()

    suffix_neighbors_set = find_neighbors_with_expected_hamming_distance(suffix(pattern), expected_hamming_distance)

    for suffix_neighbor in suffix_neighbors_set:

        if find_hamming_distance(suffix(pattern), suffix_neighbor) &lt; expected_hamming_distance:

            for nucleotide in unique_nucleotides:
                neighborhood_set.add(nucleotide + suffix_neighbor)

        else:
            neighborhood_set.add(first_symbol(pattern) + suffix_neighbor)

    if (pattern, expected_hamming_distance) not in dp_map_that_stores_all_neighbors_with_expected_hamming_distance.keys():
        dp_map_that_stores_all_neighbors_with_expected_hamming_distance[
            (pattern, expected_hamming_distance)] = neighborhood_set

    return neighborhood_set
    
</code></pre>
<p><strong>I want your suggestion on my time complexity calculation:</strong></p>
<p>For a given pattern of length <strong>N</strong> and <strong>D</strong> as maximum expected hamming distance, I calculated time complexity as -</p>
<p><span class="math-container">$\sum_{n=1}^N$</span> <span class="math-container">$\sum_{d=1}^D$</span> <span class="math-container">$n\choose d$</span> * <span class="math-container">$3^i$</span></p>
<p><strong>Reasoning:</strong> For any length <strong>n</strong>, we will choose any <strong>d</strong> letters (nucleotide in this case) to be replaced with the other 3 nucleotides that is different from the nucleotide present at that particular position.</p>
<p>For example: Pattern = ATGCAT and <strong>D</strong> = 2, then suppose for one of the case, I select 2nd and 4th positions to be replaced.</p>
<p>Then, at the second position (current nucleotide = 'T'), I can substitute any nucleotide from the set {'A', 'C', 'G'} and</p>
<p>for fourth position (current nucleotide = 'C'), I can substitute any nucleotide from the set {'A', 'T', 'G'}.</p>
<p><strong>Kindly tell me if this approach is correct?</strong></p>
<p><strong>EDIT:</strong></p>
<p>I have provided the pseudocode for the <strong>Neighbors</strong> function as follows:</p>
<pre><code>Neighbors(Pattern, d)
    if d = 0
        return {Pattern}
    if |Pattern| = 1 
        return {A, C, G, T}
    Neighborhood ← an empty set
    SuffixNeighbors ← Neighbors(Suffix(Pattern), d)
    for each string Text from SuffixNeighbors
        if HammingDistance(Suffix(Pattern), Text) &lt; d
            for each nucleotide x
                add x • Text to Neighborhood
        else
            add FirstSymbol(Pattern) • Text to Neighborhood
    return Neighborhood
</code></pre>
<p>The symbol • means concatenation of 2 strings. For example, 'S' • 'V' = 'SV'.</p>
<p>If we remove the first symbol of Pattern (denoted FirstSymbol(Pattern)), then we will obtain a</p>
<p>(k − 1)-mer that we denote by Suffix(Pattern).</p>
<p><strong>Illustration:</strong></p>
<p>Given pattern = 'ACG'</p>
<p>Expected Hamming distance (D) = 1</p>
<p>Answer = {'CCG', 'TCG', 'GCG', 'AAG', 'ATG', 'AGG', 'ACA', 'ACC', 'ACT', 'ACG'}</p>
<p>Note that the Answer is a set of all strings who have hamming distance of 1 with respect to the given pattern 'ACG'.</p>

CC BY-SA 4.0
2021-07-01T04:02:30.050Z
I'm confused by the "expectation" part. Isn't this deterministic?
Throckmorton
CC BY-SA 4.0
2021-07-01T04:10:35.663Z
Also, I'd recommend adding a pseudocode explanation of your approach in addition to the python code.
Throckmorton
CC BY-SA 4.0
2021-07-01T12:54:04.073Z
@Throckmorton, thank you very much for having a look. I have added the pseudocode with an illustration.
Deepak Tatyaji Ahire
<python><k-mer><algorithms>
Time complexity of the Neighbors function
# Time complexity of the Neighbors function

(Asked by: username_0 on 2021-06-30)

I implemented the following find_neighbors_with_expected_hamming_distance function that generates all k-mers of Hamming distance at most d from the given Pattern.
from .Hamming_Distance import find_hamming_distance

dp_map_that_stores_all_neighbors_with_expected_hamming_distance = {}

unique_nucleotides = {'A', 'C', 'G', 'T'}


def suffix(pattern):
    if len(pattern) <= 1:
        return None
    else:
        return pattern[1: (len(pattern))]


def first_symbol(pattern):
    if len(pattern) == 0:
        return None
    else:
        return pattern[0]


def find_neighbors_with_expected_hamming_distance(pattern, expected_hamming_distance):
    if expected_hamming_distance == 0:
        return {pattern}

    if len(pattern) == 1:
        return {'A', 'C', 'G', 'T'}

    if (pattern, expected_hamming_distance) in dp_map_that_stores_all_neighbors_with_expected_hamming_distance.keys():
        return dp_map_that_stores_all_neighbors_with_expected_hamming_distance[(pattern, expected_hamming_distance)]

    neighborhood_set = set()

    suffix_neighbors_set = find_neighbors_with_expected_hamming_distance(suffix(pattern), expected_hamming_distance)

    for suffix_neighbor in suffix_neighbors_set:

        if find_hamming_distance(suffix(pattern), suffix_neighbor) < expected_hamming_distance:

            for nucleotide in unique_nucleotides:
                neighborhood_set.add(nucleotide + suffix_neighbor)

        else:
            neighborhood_set.add(first_symbol(pattern) + suffix_neighbor)

    if (pattern, expected_hamming_distance) not in dp_map_that_stores_all_neighbors_with_expected_hamming_distance.keys():
        dp_map_that_stores_all_neighbors_with_expected_hamming_distance[
            (pattern, expected_hamming_distance)] = neighborhood_set

    return neighborhood_set
    

I want your suggestion on my time complexity calculation:
For a given pattern of length N and D as maximum expected hamming distance, I calculated time complexity as -
$\sum_{n=1}^N$ $\sum_{d=1}^D$ $n\choose d$ * $3^i$
Reasoning: For any length n, we will choose any d letters (nucleotide in this case) to be replaced with the other 3 nucleotides that is different from the nucleotide present at that particular position.
For example: Pattern = ATGCAT and D = 2, then suppose for one of the case, I select 2nd and 4th positions to be replaced.
Then, at the second position (current nucleotide = 'T'), I can substitute any nucleotide from the set {'A', 'C', 'G'} and
for fourth position (current nucleotide = 'C'), I can substitute any nucleotide from the set {'A', 'T', 'G'}.
Kindly tell me if this approach is correct?
EDIT:
I have provided the pseudocode for the Neighbors function as follows:
Neighbors(Pattern, d)
    if d = 0
        return {Pattern}
    if |Pattern| = 1 
        return {A, C, G, T}
    Neighborhood ← an empty set
    SuffixNeighbors ← Neighbors(Suffix(Pattern), d)
    for each string Text from SuffixNeighbors
        if HammingDistance(Suffix(Pattern), Text) < d
            for each nucleotide x
                add x • Text to Neighborhood
        else
            add FirstSymbol(Pattern) • Text to Neighborhood
    return Neighborhood

The symbol • means concatenation of 2 strings. For example, 'S' • 'V' = 'SV'.
If we remove the first symbol of Pattern (denoted FirstSymbol(Pattern)), then we will obtain a
(k − 1)-mer that we denote by Suffix(Pattern).
Illustration:
Given pattern = 'ACG'
Expected Hamming distance (D) = 1
Answer = {'CCG', 'TCG', 'GCG', 'AAG', 'ATG', 'AGG', 'ACA', 'ACC', 'ACT', 'ACG'}
Note that the Answer is a set of all strings who have hamming distance of 1 with respect to the given pattern 'ACG'.

**Tags:** python, k-mer, algorithms
> **Comments:**
> **username_1**: I'm confused by the "expectation" part. Isn't this deterministic?  
> **username_1**: Also, I'd recommend adding a pseudocode explanation of your approach in addition to the python code.  
> **username_0**: @Throckmorton, thank you very much for having a look. I have added the pseudocode with an illustration.  

---

## 1 answers

### Answer by username_1 on 2021-07-01. Score: 2 | Accepted answer

Let's first establish a lower bound on any solution:

Given a hamming distance $D$ and an input pattern $P$ of length $N$, there are $\sum\_{k=0}^D{N \choose k} 3^k$ other strings within hamming distance $D$ of $P$. Of course in the worst case, when $D=N$, there are $4^n$ possible strings.
We can also get a closed bound on the number of solutions. We can show that the sum of the first $D$ binomial coefficients for a fixed $N$ is bounded by ${N \choose D} {N-(D-1) \over N-(2D-1)}$ as shown [here](https://mathoverflow.net/a/17236). Therefore we have the following closed upper bound on the number of strings within hamming distance $D$ of some pattern of length $N$

$$
\sum\_{k=0}^D{N \choose k} 3^k \leq {N \choose D} {3^D (N-(D-1)) \over N-(2D-1)} \leq \left(\frac{3N}{D}\right)^D {N-(D-1) \over N-(2D-1)}
$$

However, for your approach, you are going through recursively, so when the subproblem is on strings within $D$ of the suffix of length $n$, you have $\sum\_{k=0}^D{n \choose k} 3^k$ of these. Given that you have $N$ subproblems (suffixes), at first glance it does indeed look like you have roughly $\sum\_{n=1}^N\sum\_{k=0}^D{n \choose k} 3^k$ iterations of the innermost for loop. However, in that `for` loop, you are also computing the Hamming Distance function, which is $O(n)$. This means that you have roughly

$$
\sum\_{n=1}^Nn\sum\_{k=0}^D{n \choose k} 3^k
$$

computations.

I would suggest finding a way to get rid of having to compute the hamming function. Since you are constructing the sequences yourself, you can keep track of each sequences hamming distance from the pattern during construction.

> **Comments:**
> **username_0**: Excellent! I missed the complexity for computing Hamming distance. Also, you can correct the first sentence - "Given a hamming distance  D"  
> **username_0**: Thank you very much @Throckmorton.  

---

