total number of occurrences of Pattern in Text with at most d mismatches.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##Our goal now is to modify our previous algorithm for the Frequent Words Problem in order to find DnaA boxes \n",
    "#by identifying frequent k-mers, possibly with mismatches. \n",
    "\n",
    "##Given strings Text and Pattern as well as an integer d, we define Countd(Text, Pattern) as the total number of \n",
    "#occurrences of Pattern in Text with at most d mismatches. For example, Count1(AACAAGCTGATAAACATTTAAAGAG, AAAAA) = 4 \n",
    "#because AAAAA appears four times in this string with at most one mismatch: AACAA, ATAAA, AAACA, and AAAGA. \n",
    "\n",
    "##Note that two of these occurrences overlap.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def hamming_distance(s1, s2):\n",
    "    if len(s1) != len(s2):\n",
    "        raise ValueError(\"Input strings must have equal length\")\n",
    "    \n",
    "    distance = 0\n",
    "    for i in range(len(s1)):\n",
    "        if s1[i] != s2[i]:\n",
    "            distance += 1\n",
    "    return distance\n",
    "\n",
    "def approximate_pattern_count(text, pattern, d):\n",
    "    count = 0\n",
    "    k = len(pattern)\n",
    "    for i in range(len(text) - k + 1):\n",
    "        subtext = text[i:i + k]\n",
    "        if hamming_distance(pattern, subtext) <= d:\n",
    "            count += 1\n",
    "    return count\n",
    "\n",
    "# Read inputs from a text file\n",
    "with open(\"F:\\Download Folder\\practice.txt\", 'r') as file:\n",
    "    pattern = file.readline().strip()\n",
    "    text = file.readline().strip()\n",
    "    d = int(file.readline().strip())\n",
    "\n",
    "# Count the occurrences with at most d mismatches\n",
    "count = approximate_pattern_count(text, pattern, d)\n",
    "print(count)\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}