d-Neighborhood of a String

Given a DNA string pattern and an integer $d$ , find the collection of strings that are within a $d$ -neighborhood of the given pattern. A $d$ -neighborhood is the set of all $k$ -mers whose Hamming distance from the pattern is at most $d$ .

Parameters

$n$ : length of string
$d$ : neighborhood distance threshold
$\sigma$ : size of alphabet

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Iterative naive	1940	$O(f_{bin}(\sigma-1, n, d))$ where $f_{bin}(x, y, z) = \sum_{i=0}^z \binom{y}{i}x^i$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms