search

tacitvenom / genomics_algo

MIT License
1 stars 1 forks source link

Implement Approximate Matching #16

Open tacitvenom opened 3 years ago

tacitvenom commented 3 years ago

Approximate Pattern Matching Problem: Find all approximate occurrences of a pattern in a string.

Input: Strings Pattern and Text along with an integer d. Output: All starting positions where Pattern appears as a substring of Text with at most d mismatches.

tacitvenom commented 3 years ago

ApproximatePatternCount(Text, Pattern, d) count ← 0 for i ← 0 to |Text| − |Pattern| Pattern′ ← Text(i , |Pattern|) if HammingDistance(Pattern, Pattern′) ≤ d count ← count + 1 return count