frequent-words-problem.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/heispv/bioinformatics/blob/master/frequent-words-problem.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vqIKaRp3rcRa"
      },
      "source": [
        "\n",
        "```\n",
        "FrequencyTable(Text, k)\n",
        "    freqMap ← empty map\n",
        "    n ← |Text|\n",
        "    for i ← 0 to n − k\n",
        "        Pattern ← Text(i, k)\n",
        "        if freqMap[Pattern] doesn't exist\n",
        "            freqMap[Pattern]← 1\n",
        "        else\n",
        "           freqMap[pattern] ←freqMap[pattern]+1\n",
        "    return freqMap\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1qxLYxZSb6Fd"
      },
      "source": [
        "```\n",
        "BetterFrequentWords(Text, k)\n",
        "    FrequentPatterns ← an array of strings of length 0\n",
        "    freqMap ← FrequencyTable(Text, k)\n",
        "    max ← MaxMap(freqMap)\n",
        "    for all strings Pattern in freqMap\n",
        "        if freqMap[pattern] = max\n",
        "            append Pattern to frequentPatterns\n",
        "    return frequentPatterns\n",
        "```"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "fWJRaRXu0UOY"
      },
      "outputs": [],
      "source": [
        "import numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "apYRDE0zrdvP"
      },
      "outputs": [],
      "source": [
        "def freq_table(text, k):\n",
        "  table = {}\n",
        "  n = len(text)\n",
        "\n",
        "  for i in range(n - k + 1):\n",
        "    pattern = text[i : i+k]\n",
        "\n",
        "    if pattern not in table.keys():\n",
        "      table[pattern] = 1\n",
        "    else:\n",
        "      table[pattern] += 1\n",
        "\n",
        "  return table"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "id": "8Du3x1blb-ur"
      },
      "outputs": [],
      "source": [
        "def best_patterns(text, k):\n",
        "  best_patterns = []\n",
        "  table = freq_table(text, k)\n",
        "  max = np.max(list(table.values()))\n",
        "\n",
        "  for key, value in table.items():\n",
        "    if value == max:\n",
        "      best_patterns.append(key)\n",
        "\n",
        "  return best_patterns"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "tv3hmCIUz1P2"
      },
      "outputs": [],
      "source": [
        "text = 'ATATTAGCTATTGGCTGATTGGCTGACGACGCAGCATATTAGCTATATTAGCTATATTAGCTACTACGGTACGACGCAGCATATTAGCTATATTAGCTATATTAGCTACGACGCAGCTGCAGTAGACGACGCAGCACGACGCAGCATATTAGCTATTGGCTGTGCAGTAGATTGGCTGACTACGGTATTGGCTGACGACGCAGCATATTAGCTACTACGGTACGACGCAGCACGACGCAGCTGCAGTAGACTACGGTATTGGCTGATATTAGCTATTGGCTGTGCAGTAGACGACGCAGCTGCAGTAGATTGGCTGACTACGGTTGCAGTAGTGCAGTAGTGCAGTAGACTACGGTATTGGCTGACTACGGTACTACGGTACTACGGTTGCAGTAGATATTAGCTATTGGCTGATATTAGCTTGCAGTAGACTACGGTATATTAGCTACTACGGTATTGGCTGATTGGCTGACGACGCAGCATATTAGCTTGCAGTAGATATTAGCTTGCAGTAGTGCAGTAGATATTAGCTACTACGGTACTACGGTACTACGGTATTGGCTGACGACGCAGCACTACGGTATTGGCTGACGACGCAGCATTGGCTGATTGGCTGACGACGCAGCACGACGCAGCACGACGCAGCACGACGCAGCATATTAGCTATATTAGCTACGACGCAGCATTGGCTGACGACGCAGCATATTAGCTTGCAGTAGACGACGCAGCATATTAGCTACGACGCAGCATTGGCTGTGCAGTAGACGACGCAGCATATTAGCTTGCAGTAGTGCAGTAGATATTAGCTTGCAGTAGACGACGCAGCATTGGCTGACGACGCAGCTGCAGTAGACGACGCAGCACGACGCAGCACGACGCAGCATTGGCTGATTGGCTGTGCAGTAGACTACGGTATATTAGCTACTACGGTATTGGCTGATATTAGCTTGCAGTAG'\n",
        "k = 12"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fPo-rWj00Kcp",
        "outputId": "bf8a61d8-d368-4e6d-8117-6c80cc6d19ab"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "['ACGACGCAGCAT']"
            ]
          },
          "execution_count": 10,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "best_patterns(text, k)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wyPAGnGc0iMh"
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "authorship_tag": "ABX9TyN139U0iyMfitN8cBd5j/n3",
      "include_colab_link": true,
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.4"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}