Rosalind_Bioinformatics_Stronghold.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Rosalind - Bioinformatics Stronghold.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "O1Awf-x9G9wZ",
        "2U2BAeAnLyxo",
        "g1QINS8qVVtw",
        "9-GLsAQT7S3F"
      ],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/cmrn-rhi/bioinformatics-practice/blob/master/Rosalind_Bioinformatics_Stronghold.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j-qmRXLGg55q",
        "colab_type": "text"
      },
      "source": [
        "*Rhiannon Cameron - [Rosalind Progress Profile](http://rosalind.info/users/cmrn-rhi/)*\n",
        "\n",
        "*Python 3.6*"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HuN1QMZug2fN",
        "colab_type": "text"
      },
      "source": [
        "# Bioinformatics Stronghold\n",
        "Learning bioinformatics and programming through problem solving"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "90pldazEhW0K",
        "colab_type": "text"
      },
      "source": [
        "## Counting DNA Nucleotides\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H8RQYwqnjbMb",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/dna/)\n",
        "\n",
        "A string is simply an ordered collection of symbols selected from some alphabet and formed into a word; the length of a string is the number of symbols that it contains.\n",
        "\n",
        "An example of a length 21 DNA string (whose alphabet contains the symbols 'A', 'C', 'G', and 'T') is \"ATGCTTCAGAAAGGTCTTACG.\"\n",
        "\n",
        "**Given:** A DNA string s of length at most 1000 nt.\n",
        "\n",
        "**Return:** Four integers (separated by spaces) counting the respective number of times that the symbols 'A', 'C', 'G', and 'T' occur in s.\n",
        "\n",
        "<h4> Sample Dataset </h4>\n",
        "\n",
        "```\n",
        "AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGATAGCAGC\n",
        "```\n",
        "\n",
        "<h4> Sample Output </h4>\n",
        "\n",
        "```\n",
        "20 12 17 21\n",
        "```\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L9Dkm4q66jQe",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 1 </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UHakkLukknXy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import collections\n",
        "\n",
        "def dna_nuc_count(dna_string):\n",
        "  \"\"\"\n",
        "  DNA Nucleotide Count\n",
        "  \n",
        "  Given: A DNA string (A, C, G, T) s of length at most 1000 nt.\n",
        "  Return: Four integers (separated by spaces) counting the respective number of\n",
        "          times that symbols 'A','C','G', and 'T' occur in s.\n",
        "  \"\"\"\n",
        "  # ensure incoming data are all uppercase\n",
        "  dna_string.upper()\n",
        "  \n",
        "  # create orderws dictionary to ensure correct output order\n",
        "  dna_dict = collections.OrderedDict()\n",
        "  dna_dict['A'] = 0\n",
        "  dna_dict['C'] = 0\n",
        "  dna_dict['G'] = 0\n",
        "  dna_dict['T'] = 0\n",
        "  \n",
        "  # count nucleotides and store associated count in dictionary\n",
        "  for nucleotide in dna_string:\n",
        "      dna_dict[nucleotide] += 1\n",
        "  \n",
        "  # return nucleotide counts separated by spaces\n",
        "  return ' '.join([str(i) for i in dna_dict.values()])\n",
        "  \n",
        "  \n",
        "  \"\"\"\n",
        "  Alternative Ouput\n",
        "  Returns nucleotide counts separated by spaces; better format for inputing\n",
        "          parameters in future functions. Works with unordered Dictionary.\n",
        "  \n",
        "  \"\"\"\n",
        "  # return dna_dict['A'], dna_dict['C'], dna_dict['G'], dna_dict['T']"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "93eLqlb1m3gk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset Test\n",
        "\n",
        "test_string = 'AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGATAGCAGC'\n",
        "dna_nuc_count(test_string)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o8vcGKQDzgCz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Dataset Test\n",
        "\n",
        "test_string = 'GAAGGAATGGGCTCATGCTGGTTTGCCCAACGGCTCCTCAACATGAAAGCCTGAAGTACACGTGAGATATATACCATTCCATACGCACCCGCGTACCGGGCATGGGAGTACAACCTGACGGCTCCGGCCGTGAGATCGGGTCATCTTGGCAGTGACACTAGGATGTTACAGGGTTAACGGACAGTTTGAACGCAGCTGTGATGGCGGCGAGCAATGAACTCAATCCATCACGAGTCACCTGGGTTAAACGGAGTATAAAGCTACTTCCGTCGGACTGGTCTTGTGGTCTGAGAAAATTGGATCGTCCGGCGAGACTAGTCCGGTACTCGAGTTAGGGTTCGCATTCCCGGGCTTTCCTCAGAGGGCTCACTACCTAGTGAACTTAGGAAGATCTACTCTGTGCGGCGTGTCAATTAGACAATGCTTTATGGAACGGGGCACTGGACAATTAGTGGTAAAAACTGAATCGCCCCCACGTGAAACTGCTCACGCTACATGCTGAATTGTTAACCCCTATAACAGTCTCTGTCAGGACTAGAACGGCTGGCGATCATATCCGGCGACGACTTTGCTCTCGTTTCAGAGGTATTGATCCTGCAGGCAGAAGGCGACCCCCGATTTTCATTCCTTTCCTGGTGTCATTTTGCTCAATATGGTATGATATAAGGTAGATGCGAATGTGTCTATATGTTGTCGAGCGCGCTTAGCCATTCGGTCACGCGTATTGACCATGGTTCGTCTAGATCATCACCCTCTCATAAGAGGAATGCCCCGGCAAGCAAGGGTGTCGCGTTTAGGGAGACTTTGTTGCCATAGCACGTGGAGAGAGTAAGAGGGGAAGCGCATAAGCGGGTGCTACGACCCGAAGCTGTCTCGGATGGCTATGTATCCTGGGGTAGGGACAGTAGAAAAGCGTGTAATGGCCGATACATCAGTCGCAATCCCGGGGCGTAGCTCTCGATAACTCTCCT'\n",
        "dna_nuc_count(test_string)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7391Ar7aw5ec",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Dataset Test - From File\n",
        "\n",
        "with open('rosalind_dna.txt') as infile:\n",
        "  test_string = infile.readline()\n",
        "  test_string_clean = test_string.rstrip('\\n')\n",
        "  print(dna_nuc_count(test_string_clean))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WGGlbsB96mhE",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 2 (Better) </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uZ8FG99658-M",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dna_nuc_count2(dna):\n",
        "  \"\"\"\n",
        "  DNA Nucleotide Count v2\n",
        "  \n",
        "  Given: A DNA string (A, C, G, T) s of length at most 1000 nt.\n",
        "  Return: Four integers (separated by spaces) counting the respective number of\n",
        "          times that symbols 'A','C','G', and 'T' occur in s.\n",
        "  \"\"\"\n",
        "  return dna.count(\"A\"), dna.count(\"G\"), dna.count(\"C\"), dna.count(\"T\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BgPTt3l46q-p",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 3 (Simple) </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8D4_tDu-6_o5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n",
        "print(*map(input().count, \"ACGT\"))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "axnALBkR7-Id",
        "colab_type": "text"
      },
      "source": [
        "## Transcribing DNA into RNA\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9Hka60fW8FlN",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/rna/)\n",
        "\n",
        "An RNA string is a string formed from the alphabet containing 'A', 'C', 'G', and 'U'.\n",
        "\n",
        "Given a DNA string t corresponding to a coding strand, its transcribed RNA string u is formed by replacing all occurrences of 'T' in t with 'U' in u.\n",
        "\n",
        "**Given:** A DNA string t having length at most 1000 nt.\n",
        "\n",
        "**Return:** The transcribed RNA string of t.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "GATGGAACTTGACTACGTAAATT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "GAUGGAACUUGACUACGUAAAUU\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ODcLFD1YFZlg",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 1 </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "htX3Hk0eBZKH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dna_to_rna(dna_string):\n",
        "  \"\"\"\n",
        "  Given: a DNA string (A, C, G, T), having length of at most 1000 nt.\n",
        "  Return: the transcribed RNA (A, C, G, U) string.\n",
        "  \n",
        "  \"\"\"\n",
        "  rna_string = ''\n",
        "  \n",
        "  for nucleotide in dna_string:\n",
        "    if nucleotide == 'T':\n",
        "      rna_string += 'U'\n",
        "    else:\n",
        "      rna_string += nucleotide\n",
        "      \n",
        "  return rna_string"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gLb2A__wDA5u",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset Test\n",
        "\n",
        "test_string = 'GATGGAACTTGACTACGTAAATT'\n",
        "dna_to_rna(test_string)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oYVcp_sODRlA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Dataset Test\n",
        "\n",
        "dna_to_rna(input())"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7GcOiUHVFpcO",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 2 </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JSl4lxkDE9nW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# User Input\n",
        "\n",
        "dna_string = input()\n",
        "print(dna_string.replace(\"T\", \"U\"))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ru8BHjyDGUom",
        "colab_type": "code",
        "outputId": "2367c8a9-cc74-47cf-f208-1db10153cc89",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 71
        }
      },
      "source": [
        "# From File\n",
        "\n",
        "with open('rosalind_rna.txt') as infile:\n",
        "  print(infile.read().replace(\"T\", \"U\"))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "UAUUUGCUAACCAUAGACCGAGAAGUCAACAAAUCGUGAAGCGUGACUAUUUCGGGCGCUACUUCACCCCGACGCCCGGCAUUUCACGCUUGGUGUGUACUACCACGGGGCCGCGGCGGAAUCCCACGCGGAGCUAACCCGUUGGGAUCAUGCAUGCGCCUCUCGGUGGUCAACGGAUGAACUAGUACACCGUCGACGUAAACAAGCUUAUCGCUACCUGGAGGAUUACUGCUGAACUAGUAAACCGGUACCCGGUAAGCCGAAUGCCUGUGAUCGAUGAGUUCUGGGUGUGCAGGAAGUACAUCGGUUAAAGUCUUGGCAGACAACUACCUUAUUUGUCCCCCAGGUGGAAUUACGAGGUGAGGCACUGACGGUAUAACAAGGAAGAGCAAUCAUUUUACACCGGACCUGUGGCCAACACCAAGGCACAGCAGUAUGCGGGAAUGACGCAAAGUCUUUGCACGAGACGGGCAAGCAGUGGCUGUAAAGUUGGACACAGUUGACUACAUUAGAGAUCUAAUACGCGUUCCAUAUCCGACUGGAGCUGGCUAAACAGGUAGAACACAUCGGCCAUUAGCAGAAGCUGUUGAAUUUGGAUCUAAUCCAAAACUAAACUCCAGUUAUGAACUCCCAAAUGAACACAACUCUCGGCGCCCAGUAGAAAUUCGUGCCUCAUUGUUCGGCGCUUGGUACACGUCGGGGCCUGGUGAGUAGUAUAGAUUUGCGCUCGUACAUUACUUCCCGCGCCGCGGGGAGAGUUUUAAAACGUGGUCUACUUGGGAUCUGAGCCUGAUAUGAAAUGGGAGAUGACAUCAGUGUACGGCGCAGCCGCACACGUCAGAAACGAAUAACUUUUUCGUAGCGCCAUUUGCCAAAGGGCUGAUUGUUGAUUGAGGAGCUCAAUCGUAUUGUAAGUCACUUGACAGCCCCUGCCUCUGGA\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dl2frkH3F9Ge",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version - Bash </h4>\n",
        "\n",
        "`tr T U < rosalind_rna.txt`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O1Awf-x9G9wZ",
        "colab_type": "text"
      },
      "source": [
        "## Complementing a Strand of DNA"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J1ETi4Z3HRT-",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/revc/)\n",
        "\n",
        "In DNA strings, symbols 'A' and 'T' are complements of each other, as are 'C' and 'G'.\n",
        "\n",
        "The reverse complement of a DNA string s is the string sc formed by reversing the symbols of s, then taking the complement of each symbol (e.g., the reverse complement of \"GTCA\" is \"TGAC\").\n",
        "\n",
        "**Given:** A DNA string s of length at most 1000 bp.\n",
        "\n",
        "**Return:** The reverse complement sc of s.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "AAAACCCGGT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "ACCGGGTTTT\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oXhAFqoHNDJ5",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 1 </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Vk6jmw8jHTDS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dna_rev_comp(dna_str):\n",
        "  \"\"\"\n",
        "  DNA Reverse Complement\n",
        "  \n",
        "  Given: a DNA string (A, C, G, T) of length at most 1000 bp.\n",
        "  Return: the reverse complement (rev_comp) of the DNA string.\n",
        "  \"\"\"\n",
        "  \n",
        "  # t & c temporarily hold positions; t will become T and c will become C\n",
        "  temp_str = dna_str.replace(\"A\", \"t\").replace(\"G\", \"c\")\n",
        "  temp_str2 = temp_str.replace(\"T\", \"A\").replace(\"C\", \"G\")\n",
        "  comp_str = temp_str2.replace(\"t\", \"T\").replace(\"c\", \"C\")\n",
        "  \n",
        "  return comp_str[::-1]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eEUNujRuKJIg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset Test\n",
        "\n",
        "test_string = 'AAAACCCGGT'\n",
        "dna_rev_comp(test_string)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y93bAOn7I0OI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# From File\n",
        "\n",
        "with open('rosalind_revc.txt') as infile:\n",
        "  print(dna_rev_comp(infile.read()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_zy1u-4qNHto",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 2 (Better) </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UzzwRwxNNMHw",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dna_rev_comp2(dna_str):\n",
        "  \"\"\"\n",
        "  DNA Reverse Complement v2\n",
        "  \n",
        "  Given: a DNA string (A, C, G, T) of length at most 1000 bp.\n",
        "  Return: the reverse complement (rev_comp) of the DNA string.\n",
        "  \"\"\"\n",
        "  \n",
        "  # t & c temporarily hold positions; t will become T and c will become C\n",
        "  comp_str = dna_str.replace(\"A\", \"t\").replace(\"G\", \"c\").replace(\"T\", \"A\")\\\n",
        "             .replace(\"C\", \"G\").replace(\"t\", \"T\").replace(\"c\", \"C\")\n",
        "  \n",
        "  return comp_str[::-1]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RQTumX4_N2MW",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 3 (Best) </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zIE2eKnAN46f",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dna_rev_comp3(dna_str):\n",
        "  \"\"\"\n",
        "  DNA Reverse Complement v3\n",
        "  \n",
        "  Given: a DNA string (A, C, G, T) of length at most 1000 bp.\n",
        "  Return: the reverse complement (rev_comp) of the DNA string.\n",
        "  \"\"\"\n",
        "  comp_str = { \"A\" : \"T\", \"C\" : \"G\", \"G\" : \"C\", \"T\" : \"A\" }\n",
        "\n",
        "  return \"\".join([comp_str[n] for n in dna_str][::-1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2U2BAeAnLyxo",
        "colab_type": "text"
      },
      "source": [
        "## Rabbits & Recurrence Relations"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "neKfDXuXL7KN",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/fib/)\n",
        "\n",
        "A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite.\n",
        "\n",
        "A recurrence relation is a way of defining the terms of a sequence with respect to the values of previous terms. In the case of Fibonacci's rabbits from the introduction, any given month will contain the rabbits that were alive the previous month, plus any new offspring. A key observation is that the number of offspring in any month is equal to the number of rabbits that were alive two months prior. As a result, if Fn represents the number of rabbit pairs alive after the n-th month, then we obtain the Fibonacci sequence having terms Fn that are defined by the recurrence relation Fn=Fn−1+Fn−2 (with F1=F2=1 to initiate the sequence).\n",
        "\n",
        "When finding the n-th term of a sequence defined by a recurrence relation, we can simply use the recurrence relation to generate terms for progressively larger values of n. This problem introduces us to the computational technique of dynamic programming, which successively builds up solutions by using the answers to smaller cases.\n",
        "\n",
        "**Given:** Positive integers n≤40 and k≤5.\n",
        "\n",
        "**Return:** The total number of rabbit pairs that will be present after n months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair).\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "5 3\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "19\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jYKOhcEKM6aW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def fib_recur(n, k):\n",
        "  \"\"\"\n",
        "  Fibonacci Recursion\n",
        "  \n",
        "  Given: Positive integers n <= 40 and K <= 5\n",
        "    n = months\n",
        "    k = rabbit pairs\n",
        "  Return: the total number of rabbit pairs that will be present after n months,\n",
        "          if we begin with 1 pair and in each generation, every pair of \n",
        "          reproduction-age rabbits produces a litter of k rabbits.\n",
        "  \"\"\"\n",
        "  # Case for when pair matures and is not yet producing offspring\n",
        "  if n == 0 or n == 1:\n",
        "    return n\n",
        "  # Case for when mature pair produces offspring, adjusted for k\n",
        "  else:\n",
        "    return fib_recur(n-1, k) + fib_recur(n-2, k)*k\n",
        " "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HTGvlC6HRhB6",
        "colab_type": "code",
        "outputId": "d1063adb-cb40-4f8a-d475-a98144a12d0a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "fib_recur(29, 5)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1850229480761"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "biyk7bhqm3LS"
      },
      "source": [
        "## Computing GC Content"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Djoyajjvm3LR"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/gc/)\n",
        "\n",
        "The GC-content of a DNA string is given by the percentage of symbols in the string that are 'C' or 'G'. For example, the GC-content of \"AGCTATAG\" is 37.5%. Note that the reverse complement of any DNA string has the same GC-content.\n",
        "\n",
        "DNA strings must be labeled when they are consolidated into a database. A commonly used method of string labeling is called FASTA format. In this format, the string is introduced by a line that begins with '>', followed by some labeling information. Subsequent lines contain the string itself; the first line to begin with '>' indicates the label of the next string.\n",
        "\n",
        "In Rosalind's implementation, a string in FASTA format will be labeled by the ID \"Rosalind_xxxx\", where \"xxxx\" denotes a four-digit code between 0000 and 9999.\n",
        "\n",
        "**Given**: At most 10 DNA strings in FASTA format (of length at most 1 kbp each).\n",
        "\n",
        "**Return**: The ID of the string having the highest GC-content, followed by the GC-content of that string. Rosalind allows for a default error of 0.001 in all decimal answers unless otherwise stated; please see the note on absolute error below.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        ">Rosalind_6404\n",
        "CCTGCGGAAGATCGGCACTAGAATAGCCAGAACCGTTTCTCTGAGGCTTCCGGCCTTCCC\n",
        "TCCCACTAATAATTCTGAGG\n",
        ">Rosalind_5959\n",
        "CCATCGGTAGCGCATCCTTAGTCCAATTAAGTCCCTATCCAGGCGCTCCGCCGAAGGTCT\n",
        "ATATCCATTTGTCAGCAGACACGC\n",
        ">Rosalind_0808\n",
        "CCACCCTCGTGGTATGGCTAGGCATTCAGGAACCGGAGAACGCTTCAGACCAGCCCGGAC\n",
        "TGGGAACCTGCGGGCAGTAGGTGGAAT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "\n",
        "```\n",
        "Rosalind_0808\n",
        "60.919540\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "kf_guR9Pm3LQ"
      },
      "source": [
        "<h4> Version 1 - BioPython </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "okpt497Im3LO",
        "colab": {}
      },
      "source": [
        "# install BioPython (includes NumPy).\n",
        "!pip install biopython"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "H509TMV6m3LL",
        "colab": {}
      },
      "source": [
        "# import Bio SeqIO package from BioPython.\n",
        "from Bio import SeqIO\n",
        "\n",
        "def gc_content_greatest(dna_strings):\n",
        "  \"\"\"\n",
        "  Computing Greatest GC Content\n",
        "  \n",
        "  Given: file containing <= 10 DNA strings (A, C, G, T), FASTA format,\n",
        "         length <= 1kbp/string.\n",
        "  Return: DNA string ID with the highest GC content, followed by the GC content\n",
        "          of that string. Default error of 0.001.\n",
        "          \n",
        "  nt_count = total nucleotide count of DNA string.\n",
        "  gc_count = total GC nucleotide counts of DNA string.\n",
        "  gc_percent = GC content; percent of nucleotides in DNA string that are G+C.\n",
        "  gc_greatest = DNA string with the highest GC content percent.\n",
        "  id_greatest = ID for DNA string with the highest GC content percent.\n",
        "  \"\"\"\n",
        "  gc_greatest = 0\n",
        "  \n",
        "  for seq_record in SeqIO.parse(dna_strings, \"fasta\"):\n",
        "    nt_count = len(seq_record)\n",
        "    gc_count = 0  \n",
        "\n",
        "    for nt in seq_record.seq:\n",
        "      if nt == 'G' or nt == 'C':\n",
        "        gc_count += 1\n",
        "\n",
        "    gc_percent = (gc_count/nt_count)*100\n",
        "\n",
        "    # store/update record of ID and GC% of sequence with greatest GC%\n",
        "    if gc_greatest < gc_percent:\n",
        "      gc_greatest = gc_percent\n",
        "      id_greatest = seq_record.id\n",
        "\n",
        "  print(id_greatest)\n",
        "  print(round(gc_greatest, 3)) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "_pyCJn7lm3LJ",
        "colab": {}
      },
      "source": [
        "gc_content_greatest(\"rosalind_gc.fasta\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ISzRr4-8m3LF"
      },
      "source": [
        "<h4>Version 2 - BioPython (Best)</h4>\n",
        "\n",
        "*Be sure to install package using first code block from Version 1.*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "OquEgnVtm3LA",
        "colab": {}
      },
      "source": [
        "# import Bio SeqIO package from BioPython.\n",
        "from Bio import SeqIO\n",
        "# import GC function: calculates G+C content, returns percentage as float.\n",
        "from Bio.SeqUtils import GC\n",
        "\n",
        "def gc_content_greatest2(dna_strings):\n",
        "  \"\"\"\n",
        "  Computing Greatest GC Content\n",
        "  \n",
        "  Given: file containing <= 10 DNA strings (A, C, G, T), FASTA format, length\n",
        "          <= 1kbp/string.\n",
        "  Return: DNA string ID with the highest GC content, followed by the GC content\n",
        "          of that string. Default error of 0.001.\n",
        "          \n",
        "  gc_greatest = DNA string with the highest GC content percent.\n",
        "  id_greatest = ID for DNA string with the highest GC content percent.\n",
        "  \"\"\"\n",
        "\n",
        "  gc_greatest = 0\n",
        "  id_greatest = \"\"\n",
        "\n",
        "  with open(dna_strings, 'r') as infile:\n",
        "\n",
        "    for record in SeqIO.parse(infile, \"fasta\"):\n",
        "        if gc_greatest < GC(record.seq):\n",
        "            gc_greatest = GC(record.seq)\n",
        "            id_greatest = record.id\n",
        "\n",
        "  print(id_greatest)\n",
        "  print(round(gc_greatest,3))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "9z17pCBHm3K8",
        "colab": {}
      },
      "source": [
        "gc_content_greatest2(\"rosalind_gc.fasta\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "cqigHsiFm3K6"
      },
      "source": [
        "<h4>Version 3 (Python Only)</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "wj9oCjbQm3K1",
        "colab": {}
      },
      "source": [
        "def gc_content_greatest3(dna_strings):\n",
        "  \"\"\"\n",
        "  Computing Greatest GC Content\n",
        "  \n",
        "  Given: file containing <= 10 DNA strings (A, C, G, T), FASTA format, \n",
        "         length <= 1kbp/string.\n",
        "  Return: DNA string ID with the highest GC-content, followed by the GC-content\n",
        "          of that string. Default error of 0.001.\n",
        "          \n",
        "  gc_dict = dictionary where DNA string IDs are stored as keys while associated\n",
        "            DNA string GC content is stored as values.\n",
        "  gc_percent = GC content; percent of nucleotides in DNA string that are GC.\n",
        "  seq_id = DNA string ID.\n",
        "  \"\"\"\n",
        "   \n",
        "  with open(dna_strings, 'r') as infile:\n",
        "    data = infile.read()\n",
        "    gc_dict = {}\n",
        "    \n",
        "    # iterate over sequence blocks; beginning indicated by '>'\n",
        "    for block in data.split(\">\")[1:]: \n",
        "        \n",
        "        # split data at newline; [0] is ID while [1:] is DNA string.\n",
        "        parts = block.split(\"\\n\")      \n",
        "        # assign sequence ID\n",
        "        seq_id = parts[0]  \n",
        "        # join all sequence strings into one string\n",
        "        seq = ''.join(parts[1:])\n",
        "        gc_percent = 100 * ( seq.count(\"G\") + seq.count(\"C\") ) / float(len(seq))\n",
        "        # insert sequence ID and associated GC content into dictionary\n",
        "        gc_dict[gc_percent] = seq_id\n",
        "        \n",
        "  print(gc_dict[max(gc_dict)])\n",
        "  print(round(max(gc_dict), 3))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "XxWgDZ6am3Kt",
        "colab": {}
      },
      "source": [
        "gc_content_greatest3(\"rosalind_gc.txt\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iF5bmtZFUe6g",
        "colab_type": "text"
      },
      "source": [
        "## Counting Point Mutations"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4RYxMs6mUgqx",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/hamm/)\n",
        "\n",
        "Given two strings s and t of equal length, the **Hamming distance** (the minimum number of symbol substitutions required to transform one string into the other) between s and t, denoted d<sub>H</sub>(s,t), is the number of corresponding symbols that differ in s and t. See Figure 2.\n",
        "<br />\n",
        "<br />\n",
        "\n",
        "![Figure 2.](http://rosalind.info/media/problems/hamm/Hamming_distance.png)\n",
        "\n",
        "<sub>Figure 2. The Hamming distance between these two strings is 7. Mismatched symbols are colored red.</sub>\n",
        "<br />\n",
        "<br />\n",
        "**Given**: Two DNA strings s and t of equal length (not exceeding 1 kbp).\n",
        "\n",
        "**Return**: The Hamming distance d<sub>H</sub>(s,t).\n",
        "<br />\n",
        "<br />\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "GAGCCTACTAACGGGAT\n",
        "CATCGTAATGACGGCCT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "7\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ahL--03nUi8h",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kPFRFCD_UkYA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def calc_point_mutation(s,t):\n",
        "  \"\"\"\n",
        "  Counting Point Mutations\n",
        "  \n",
        "  Given: two DNA strings (A, C, G, T) s and t of equal length (<= 1kbp).\n",
        "  Return: the hamming distance (the minimum number of symbol substitutions\n",
        "          required to transform one string into the other) between s and t.\n",
        "          \n",
        "  pt_mut = point mutation; corresponding nucleotides differ between s and t.\n",
        "  \"\"\"\n",
        "  pt_mut = 0\n",
        "  \n",
        "  for nt in range(len(s)):\n",
        "    if s[nt] != t[nt]:\n",
        "      pt_mut += 1\n",
        "  \n",
        "  return pt_mut"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HIR6bjb8UqFS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset\n",
        "\n",
        "calc_point_mutation('GAGCCTACTAACGGGAT','CATCGTAATGACGGCCT')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OFUyG9SiUq4I",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test Dataset - From File\n",
        "\n",
        "with open(\"rosalind_hamm.txt\", 'r') as infile:\n",
        "  data = infile.read()\n",
        "  # separate sequences by newlines\n",
        "  seqs = data.split(\"\\n\")\n",
        "\n",
        "calc_point_mutation(seqs[0],seqs[1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vZkA1Bq-Usu5",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 2 (Better)</h4>\n",
        "\n",
        "*'zip' iterates over tuples one at a time such that none of them remain in memory.*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4cvMeqyUUu1h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def calc_point_mutation2(s,t):\n",
        "  \"\"\"\n",
        "  Counting Point Mutations\n",
        "  \n",
        "  Given: two DNA strings (A, C, G, T) s and t of equal length (<= 1kbp).\n",
        "  Return: the hamming distance (the minimum number of symbol substitutions\n",
        "          required to transform one string into the other) between s and t.\n",
        "          \n",
        "  pt_mut = point mutation; corresponding nucleotides differ between s and t.\n",
        "  \"\"\"\n",
        "  return sum(nt1 != nt2 for nt1, nt2 in zip(s,t))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6nDstA-EUxDx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset\n",
        "calc_point_mutation2('GAGCCTACTAACGGGAT','CATCGTAATGACGGCCT')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a5S5XqC_Uy1J",
        "colab_type": "text"
      },
      "source": [
        "## Mendel's First Law"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ipNu6QqVU8Sx",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/iprb/)\n",
        "\n",
        "...\n",
        "\n",
        "**Given**: Three positive integers k, m, and n, representing a population containing k+m+n organisms: k individuals are homozygous dominant for a factor, m are heterozygous, and n are homozygous recessive.\n",
        "\n",
        "**Return**: The probability that two randomly selected mating organisms will produce an individual possessing a dominant allele (and thus displaying the dominant phenotype). Assume that any two organisms can mate.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "2 2 2\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "0.78333\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I7Og3iZtU-d5",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6frbaKQ1VBBK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dominant_allele_prob(k,m,n):\n",
        "  \"\"\"\n",
        "  Dominant Allele Probability\n",
        "  \n",
        "  Given: three positive ints k, m, and n representing interfertile populations;\n",
        "         k = indiviuals homozygous for a factor.             (e.g. AA)\n",
        "         m = individuals heterozygous for a factor.          (e.g. Aa)\n",
        "         n = individuals homozygous recessive for a factor.  (e.g. aa)\n",
        "  Return: the probability that two randomly selected mating organisms will\n",
        "          produce an individual possessing a dominant allele.\n",
        "  \"\"\"\n",
        "  \n",
        "  # punnet square dominant factor probabilities.\n",
        "    # AA+AA = 1\n",
        "    # AA+Aa = 1\n",
        "    # AA+aa = 1\n",
        "    # Aa+Aa = 0.75\n",
        "    # Aa+aa = 0.5\n",
        "    # aa+aa = 0\n",
        "  \n",
        "  total = k + m + n\n",
        "  \n",
        "  # AA+AA event\n",
        "  kk_prob = (k/total) * ((k-1)/(total-1))\n",
        "  # AA+Aa and Aa+AA events\n",
        "  km_prob = ((k/total)*(m/(total-1)) + ((m/total)*(k/(total-1))))\n",
        "  # AA+aa and aa+AA events\n",
        "  kn_prob = ((k/total) * (n/(total-1)) + ((n/total) * (k/(total-1))))\n",
        "  # Aa+Aa event\n",
        "  mm_prob = ((m/total) * ((m-1)/(total-1))) * 0.75\n",
        "  # Aa+aa and aa+Aa events\n",
        "  mn_prob = ((m/total) * (n/(total-1)) + ((n/total) * (m/(total-1)))) * 0.5\n",
        "  # aa+aa event\n",
        "  nn_prob = ((n/total) * (n/(total-1))) * 0\n",
        "  \n",
        "  return round(kk_prob + km_prob + kn_prob + mm_prob + mn_prob + nn_prob, 5)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TmkcUWD8VEYp",
        "colab_type": "code",
        "outputId": "c2e5e899-4847-41b2-f5eb-09d3e01fc8ed",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Sample Dataset\n",
        "dominant_allele_prob(2,2,2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 30
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S1_vvSJ6XxEr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test Dataset\n",
        "dominant_allele_prob(28,19,15)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i7dPnJTgVF47",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 2 (Simplier)</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9NR4UahoY8oU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dominant_allele_prob2(k,m,n):\n",
        "  \"\"\"\n",
        "  Dominant Allele Probability\n",
        "  \n",
        "  Given: three positive ints k, m, and n representing interfertile populations;\n",
        "         k = indiviuals homozygous for a factor.             (e.g. AA)\n",
        "         m = individuals heterozygous for a factor.          (e.g. Aa)\n",
        "         n = individuals homozygous recessive for a factor.  (e.g. aa)\n",
        "  Return: the probability that two randomly selected mating organisms will\n",
        "          produce an individual possessing a dominant allele.\n",
        "  \"\"\"\n",
        "  \n",
        "  # punnet square non-dominant factor probabilities.\n",
        "    # AA+AA = 0\n",
        "    # AA+Aa = 0\n",
        "    # AA+aa = 0\n",
        "    # Aa+Aa = 0.25\n",
        "    # Aa+aa = 0.5\n",
        "    # aa+aa = 1\n",
        "  \n",
        "  total = k + m + n\n",
        "  \n",
        "  # Aa+Aa event resulting in aa.\n",
        "  # (m*(m-1)*0.25) / (total*(total-1))\n",
        "  \n",
        "  # Aa+aa and aa+Aa event resulting in aa.\n",
        "  # (m*n)(m*n)*0.5 / (total*(total-1))\n",
        "  \n",
        "  # aa+aa event.\n",
        "  # n*(n-1) / (total*(total-1))\n",
        "  \n",
        "  prob_aa = (((m*n) + (m*(m-1)*0.25) + (n*(n-1))) / (total*(total-1)))\n",
        "  \n",
        "  # return 1 minus probability of non-dominant to get dominant probability.\n",
        "  return round(1 - prob_aa, 5)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3_dzyux0csOJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset\n",
        "dominant_allele_prob2(2,2,2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LuVK-b5rfQdr",
        "colab_type": "text"
      },
      "source": [
        "##Translating RNA into Protein"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YCP2gw_UfZV5",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/prot/)\n",
        "\n",
        "The 20 commonly occurring amino acids are abbreviated by using 20 letters from the English alphabet (all letters except for B, J, O, U, X, and Z). Protein strings are constructed from these 20 symbols. Henceforth, the term genetic string will incorporate protein strings along with DNA strings and RNA strings.\n",
        "\n",
        "The RNA codon table dictates the details regarding the encoding of specific codons into the amino acid alphabet.\n",
        "\n",
        "**Given**: An RNA string s corresponding to a strand of mRNA (of length at most 10 kbp).\n",
        "\n",
        "**Return**: The protein string encoded by s.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "MAMAPRTEINSTRING\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eCdGOZaylPOK",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1</h4> (1/6 Translations)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CocR6XqBlRbq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def translate_rna(rna_string):\n",
        "  \"\"\"\n",
        "  Translate RNA into Protein\n",
        "  \n",
        "  Given: an RNA string s corresponding to a strand of mRNA (length <=10 kbp).\n",
        "  Return: the protein string (amino acid chain) encoded by s.\n",
        "          (One of six possible translations)\n",
        "  \"\"\"\n",
        "  # RNA codon table\n",
        "  codon_dict = {\n",
        "    \"UUU\":\"F\",    \"CUU\":\"L\", \"AUU\":\"I\", \"GUU\":\"V\",\n",
        "    \"UUC\":\"F\",    \"CUC\":\"L\", \"AUC\":\"I\", \"GUC\":\"V\",\n",
        "    \"UUA\":\"L\",    \"CUA\":\"L\", \"AUA\":\"I\", \"GUA\":\"V\",\n",
        "    \"UUG\":\"L\",    \"CUG\":\"L\", \"AUG\":\"M\", \"GUG\":\"V\",\n",
        "    \"UCU\":\"S\",    \"CCU\":\"P\", \"ACU\":\"T\", \"GCU\":\"A\",\n",
        "    \"UCC\":\"S\",    \"CCC\":\"P\", \"ACC\":\"T\", \"GCC\":\"A\",\n",
        "    \"UCA\":\"S\",    \"CCA\":\"P\", \"ACA\":\"T\", \"GCA\":\"A\",\n",
        "    \"UCG\":\"S\",    \"CCG\":\"P\", \"ACG\":\"T\", \"GCG\":\"A\",\n",
        "    \"UAU\":\"Y\",    \"CAU\":\"H\", \"AAU\":\"N\", \"GAU\":\"D\",\n",
        "    \"UAC\":\"Y\",    \"CAC\":\"H\", \"AAC\":\"N\", \"GAC\":\"D\",\n",
        "    \"UAA\":\"stop\", \"CAA\":\"Q\", \"AAA\":\"K\", \"GAA\":\"E\",\n",
        "    \"UAG\":\"stop\", \"CAG\":\"Q\", \"AAG\":\"K\", \"GAG\":\"E\",\n",
        "    \"UGU\":\"C\",    \"CGU\":\"R\", \"AGU\":\"S\", \"GGU\":\"G\",\n",
        "    \"UGC\":\"C\",    \"CGC\":\"R\", \"AGC\":\"S\", \"GGC\":\"G\",\n",
        "    \"UGA\":\"stop\", \"CGA\":\"R\", \"AGA\":\"R\", \"GGA\":\"G\",\n",
        "    \"UGG\":\"W\",    \"CGG\":\"R\", \"AGG\":\"R\", \"GGG\":\"G\"}\n",
        "  \n",
        "  aa_chain = ''\n",
        "  \n",
        "  # find first occurence of a start codon.\n",
        "  start = rna_string.find('AUG')\n",
        "  # truncate sequence preceding start codon.\n",
        "  trim_string = rna_string[start:]\n",
        "\n",
        "  for i in range(0, len(trim_string),3):\n",
        "    codon = trim_string[i:i+3]\n",
        "    \n",
        "    if codon in codon_dict:\n",
        "      # check for stop codon.\n",
        "      if codon_dict[codon] == \"stop\":\n",
        "        break\n",
        "      # if not stop codon, add the amino acid chain.\n",
        "      else:\n",
        "        aa_chain += codon_dict[codon]\n",
        "      \n",
        "  return aa_chain"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mvFjzq7zrmY0",
        "colab_type": "code",
        "outputId": "2e80387d-d296-4999-9845-6c800ef0e9cf",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Sample Dataset\n",
        "translate_rna('AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'MAMAPRTEINSTRING'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M0295hn616Hz",
        "colab_type": "code",
        "outputId": "97766a36-bf40-4981-d5df-e5f33924fb92",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Test Dataset - From File\n",
        "with open(\"rosalind_prot.txt\", 'r') as infile:\n",
        "  data = infile.read()\n",
        "  \n",
        "translate_rna(data)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'MSSPLGWPAVGLRIVDDPGKLINLGPKTEGLRFYRRAGSGLPETFNAHKHVRRRTAIVTPTVYDKRLQTPTKHHYATAIVGDNPKLRRVLPSIRGHPTCGRHLHYEDSDSSTRMNCRRMRGLLNMLARRSSSCERRCISLQGSLFDPAGSKVSGFLDPVTQHCSITAQTPLLIFSCSHYIADNEDCSKLNFHRLFVWVLAPFTVTQYEYTPSHSAHQVQLSNRPPQSMPSVQTYINTNANRFLMRRDVTLRGSTSDGKNIGDPERGSRTRSTARASPASTSVSRIKSIKLSEDFWTYAMLCLFPIAIYCQHRPRFNYDIYGYMPIEASLLQNAKSIRWSWPLTTMVYLVKRCPEPRHESPRKTRNNVYGPNTTWGSIPHDIPAHNARPPLSLRETRSPLQYYVGRLKTKVCRISAAIQSRKNPKHSYTRMKASACYGDNCMRDSFGLSPNDSVSSGQQSFIRDYQKTASTPFVTLGYGIERNVWCLPRYQTLLTLANASQRLWAHLVVLSRTKELKSFFTINVTFFLKYIGNIDCISFRYSPTISYIYVFRIWHTGVRYVEIGTHWGGHEGALLIPTKTCFRMFLGPGTYSALGLRFLHFRNGSLCELFSHSHNGPYLQHVQYVKTESLMTLCLTDTMIEWPYNGEVLKPASRQICDCPTCRCEHWYHKSILRLPGLKNRRANNCEFICKCDLLQSTHGYRANLSMSNAKQLLSRGPSTRVWDRSKYTPRSEYTSLVFEEMMNRSRAWPNMSESISKTGRLKVRGNSDLRSDKDPVNPVADKQLKRDQLVYTCPIRTPGLCVLFIASGNIPGTYLGVSCAENEAAYKGLPRARSSSHYTPLYGSLRVGSRLADGKLGCNLSAVLDRCTRNAFRYVNIATQKPSELSSSDLLPLSQNTQNYVPSIVLWRMRDKKMDCQSVRPEVSRSSPRVEDGQVAGVAKVHKHFALRRCCHFSWLQQKLKILNHLVSFHTFSLSVERTVSPTPQPTYRIAQTYAKLTEPILVTGLYYVIKVSTKTGVHAQVARLQKVSEIGAELLGIGCVWSVYSTISVIKSRVPSSPDKPCGEKLRPRSIGYVIDINRSENGHSLSANVQLCLAPGRTRGRGESAHPYGLASPGVAVDKLQFRCLLKLLRVWWITDTYWPLLLTLSPRRRPRLLWHVRSYLTHLTLLLTDTPVPYPLTSPWRNVTNLPTPKIGWANTNNSYLHFWLEGPNGWPQTVKRGRAQLVHTKNTRHTPWKLGPRIRRPVHPSSYAGPLKLAPCTRKQRCPIWSPVLAHSLGRKQHPLRLVSKSARFHSENDTYPSRSRRSPRNQGWYCFLRSLETGVGRSLASDYPPYTRGSFCRTNCTLQTVPSSIHYNIYTACMAKYIPTFRLTPGVFDLWNCSIGARINCRSTGGCCTSPANGRVPSHRGMCQSSVTKSGRSPNMKTLPQRAKARCLKPGLRQLYPKDRCAASLTTSPIAVSKWHIVHGAPGKNVVANSYMRMIPRAPRGPPSSAPFNDYYQPILLRPSGPTRVCSNRGRAALQPVGEAASERRAVWQTASLPLYESSERIKAVRLTDEMWALQHAVKDVQLYRRECWILTILTPIGSRGLRESELKPSSSVEFFPLANSHSLGAVQWPEAIAQKPLQVSLRPNTINAVDDGSGNRLSFGTKRVPRERVNRTNRRLFIIELEFTPLRTIQGLMYPVATSSRTNGPCGWAPRFFHHSTWGHCCIYWVRSIQVKSAHIPRPDCTAPPDVIHVVESTIYSQCQAELTPQEAGAKRHTISNFLVHRALAGAMFAFRVIARGYDNRIVVRCHRNTFNRTLGRSYVGKTSSAHDTKLSGPLNANSTRKARSQTRDSLNRGPSATGRLAPRGLYIRLIILIRGTVVSICPISEVSSRVLMADTGRSGNGQSLTTSPRVSGVLRAPKHQGSSGIPLEETPTHRRHRQKTYFKHTEFQYVGRAGHESNDLLRGLAHITRSIIQKARVTASYDDTPIHHWGRQPTTVLPVDIHCILTESGLRTRSRRGRPHRRWRLIPTSLSMKYLYTLTNSQLTSGNQVLLDCILDLCQGKGHTKVSACRNAGGPYQPPLPHTLSAQVISLLGQLVVSCCWDLMRFSNGLCAGAAPRTESWMLSLFGGLRCSAKQGSKFLYVYTHCYKVTKYELSPLTSLILVPSPMQESFELFRHWRHNRLVNALSPGSLCANIQWVPTEDWQGLDVLRHQAVPVTRVAILEVIIWVNQVVDTRAPGRRSGFWGALSRWHLRVTMTYSPTVDRARRPTRTFRLTPAPPAPTIQFGTRGTKGLPFIFSLAVGRRGFRMSPPSNCKRIENTALLGNSKANGEMIVHWSRGERLFTTAYSGIGVRNPRLGRFWISIQFPPRKLHLEYPNQRHTRPWFTQERPLSRHSIIWGSRMTVHRSAPAPCLIRLLAVTIAMCSLRAWPRNYRRTVLAKAPYGSGSAGDGWSRTLAQVRWRGDVTPWRVKCSAPQLSILSNSTVCANAPTLRMLFNLRRMRHVLRKGDYSVNVTLCRAKKCKLSPGFWRRLCPVLQQKLPRRVPFPQNTVSRLQPAGCINVGWAEYIARGESWIKATIPYAELSWGTIAHPLSDRSVVPSVTAICMESRFIIPRWAVRHGFRNQFGGFSQTVLSDLLHPPALLLRDCRSANGQTFPGYFAGGARVPATAQPKFIRQCQTTNTSDLWPRAATCCSPHASSGRLQPFNILNDRLFGRLEVSAFNNLQKCACSYNPLWDEGSMLARLKQSKSCSCSPTASPTVAGKYISFSGHYSPRAVMLAYADWMTACPPRAWQKRINVAASRALSAESIVLDPDVTSDRVLSGYQIHNLRILCPVAVRTAGGDAFTVVGVNESHASHRHSCMAYLRNDWRYLVTTSQEVEAKTVMERHLHALTQDQSRPALQDYIDRIERNPLVSRVPGVGRVHAVYILSLHHGAPSNGAIQVTRLSFRWARHKKFSNSHPVFCLSARNGFPGVSPSNVISLLEAPVATYASLDDSLRRLLKSARLCVRSTCPAHQVSNITVLVEARDILVGPGESKTTSDRQFPPLRLQSLHSCHPTPGKVARFGLAKSTRVSSVRTCGSVLFQHEGHTKIPGCSWISCLVAPCTGSVVNRFQSFSRDRCSGYCLIPIRFLPASILCMLKAVRTLGCVQGAIHDRFAGFDGLKSGAPTPKGRYIRAIMAGCVETSFTLTQPLELLSGLMGCPCLVVDRMYDDISWTIHSLSTRHILMAVT'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b0FSWjE0rm-C",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 2 - BioPython (In Progress)</h4>(1/6 Translations)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6uV-tM7f3CBi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# install BioPython (includes NumPy).\n",
        "!pip install biopython"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "A4Uyj45k_AB6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from Bio.Seq import Seq\n",
        "\n",
        "def extend_seq(seq_string):\n",
        "    \"\"\" \n",
        "    Extend Sequence\n",
        "    \n",
        "    Given: DNA/RNA string.\n",
        "    Return: Original DNA/RNA string extended with 'N' such that the length is \n",
        "            a multiple of 3 if it is not already so. Avoids \"Biopython Warning:\n",
        "            Partial codon\" and potential future errors.\n",
        "    \n",
        "    \"\"\"\n",
        "    remainder = len(seq_string) % 3\n",
        "    \n",
        "    if remainder == 0:\n",
        "      return seq_string\n",
        "    else:\n",
        "      return seq_string + Seq('N' * (3 - remainder))\n",
        "      #return '\\n'.rstrip(seq_string) + str('N' * (3 - remainder))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2Y8i5RddKwRO",
        "colab_type": "text"
      },
      "source": [
        "**Issue:** Cannot currently get **extend_seq()** to work as it keeps adding a **\\n** when contatinating the return variables. This happens with string and Seq types (though it should happen with neither) and I cannot seem to successfully strip it."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pjFh8AbjEk5I",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from Bio.Seq import Seq\n",
        "\n",
        "def translate_rna(rna_string):\n",
        "  \"\"\"\n",
        "  Translate RNA into Protein\n",
        "  \n",
        "  Given: a file containing an RNA string s corresponding to a strand of mRNA \n",
        "         (length <=10 kbp).\n",
        "  Return: the protein string (amino acid chain) encoded by s One of six possible\n",
        "          tanslations). Will raise \"BiopythonWarning: Partial codon\" if trailing\n",
        "          amino acids to not form a codon but will still output protein string.\n",
        "          \n",
        "  \"\"\"  \n",
        "  with open(rna_string, 'r') as infile:\n",
        "    data = Seq(infile.read())\n",
        "    #data = infile.read()\n",
        "    \n",
        "    #data_extend = extend_seq(data)\n",
        "    #data_extend = Seq(extend_seq(data))\n",
        "  \n",
        "  return str(data.translate())[:-1]\n",
        "  #return type(data_extend), type(data)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t2URGQtiKhyr",
        "colab_type": "code",
        "outputId": "77bebbff-1895-41b7-d74e-1c5a725d6fbc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        }
      },
      "source": [
        "#Test Dataset - From File\n",
        "translate_rna(\"rosalind_prot.txt\")"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.6/dist-packages/Bio/Seq.py:2715: BiopythonWarning: Partial codon, len(sequence) not a multiple of three. Explicitly trim the sequence or add trailing N before translation. This may become an error in future.\n",
            "  BiopythonWarning)\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'MSSPLGWPAVGLRIVDDPGKLINLGPKTEGLRFYRRAGSGLPETFNAHKHVRRRTAIVTPTVYDKRLQTPTKHHYATAIVGDNPKLRRVLPSIRGHPTCGRHLHYEDSDSSTRMNCRRMRGLLNMLARRSSSCERRCISLQGSLFDPAGSKVSGFLDPVTQHCSITAQTPLLIFSCSHYIADNEDCSKLNFHRLFVWVLAPFTVTQYEYTPSHSAHQVQLSNRPPQSMPSVQTYINTNANRFLMRRDVTLRGSTSDGKNIGDPERGSRTRSTARASPASTSVSRIKSIKLSEDFWTYAMLCLFPIAIYCQHRPRFNYDIYGYMPIEASLLQNAKSIRWSWPLTTMVYLVKRCPEPRHESPRKTRNNVYGPNTTWGSIPHDIPAHNARPPLSLRETRSPLQYYVGRLKTKVCRISAAIQSRKNPKHSYTRMKASACYGDNCMRDSFGLSPNDSVSSGQQSFIRDYQKTASTPFVTLGYGIERNVWCLPRYQTLLTLANASQRLWAHLVVLSRTKELKSFFTINVTFFLKYIGNIDCISFRYSPTISYIYVFRIWHTGVRYVEIGTHWGGHEGALLIPTKTCFRMFLGPGTYSALGLRFLHFRNGSLCELFSHSHNGPYLQHVQYVKTESLMTLCLTDTMIEWPYNGEVLKPASRQICDCPTCRCEHWYHKSILRLPGLKNRRANNCEFICKCDLLQSTHGYRANLSMSNAKQLLSRGPSTRVWDRSKYTPRSEYTSLVFEEMMNRSRAWPNMSESISKTGRLKVRGNSDLRSDKDPVNPVADKQLKRDQLVYTCPIRTPGLCVLFIASGNIPGTYLGVSCAENEAAYKGLPRARSSSHYTPLYGSLRVGSRLADGKLGCNLSAVLDRCTRNAFRYVNIATQKPSELSSSDLLPLSQNTQNYVPSIVLWRMRDKKMDCQSVRPEVSRSSPRVEDGQVAGVAKVHKHFALRRCCHFSWLQQKLKILNHLVSFHTFSLSVERTVSPTPQPTYRIAQTYAKLTEPILVTGLYYVIKVSTKTGVHAQVARLQKVSEIGAELLGIGCVWSVYSTISVIKSRVPSSPDKPCGEKLRPRSIGYVIDINRSENGHSLSANVQLCLAPGRTRGRGESAHPYGLASPGVAVDKLQFRCLLKLLRVWWITDTYWPLLLTLSPRRRPRLLWHVRSYLTHLTLLLTDTPVPYPLTSPWRNVTNLPTPKIGWANTNNSYLHFWLEGPNGWPQTVKRGRAQLVHTKNTRHTPWKLGPRIRRPVHPSSYAGPLKLAPCTRKQRCPIWSPVLAHSLGRKQHPLRLVSKSARFHSENDTYPSRSRRSPRNQGWYCFLRSLETGVGRSLASDYPPYTRGSFCRTNCTLQTVPSSIHYNIYTACMAKYIPTFRLTPGVFDLWNCSIGARINCRSTGGCCTSPANGRVPSHRGMCQSSVTKSGRSPNMKTLPQRAKARCLKPGLRQLYPKDRCAASLTTSPIAVSKWHIVHGAPGKNVVANSYMRMIPRAPRGPPSSAPFNDYYQPILLRPSGPTRVCSNRGRAALQPVGEAASERRAVWQTASLPLYESSERIKAVRLTDEMWALQHAVKDVQLYRRECWILTILTPIGSRGLRESELKPSSSVEFFPLANSHSLGAVQWPEAIAQKPLQVSLRPNTINAVDDGSGNRLSFGTKRVPRERVNRTNRRLFIIELEFTPLRTIQGLMYPVATSSRTNGPCGWAPRFFHHSTWGHCCIYWVRSIQVKSAHIPRPDCTAPPDVIHVVESTIYSQCQAELTPQEAGAKRHTISNFLVHRALAGAMFAFRVIARGYDNRIVVRCHRNTFNRTLGRSYVGKTSSAHDTKLSGPLNANSTRKARSQTRDSLNRGPSATGRLAPRGLYIRLIILIRGTVVSICPISEVSSRVLMADTGRSGNGQSLTTSPRVSGVLRAPKHQGSSGIPLEETPTHRRHRQKTYFKHTEFQYVGRAGHESNDLLRGLAHITRSIIQKARVTASYDDTPIHHWGRQPTTVLPVDIHCILTESGLRTRSRRGRPHRRWRLIPTSLSMKYLYTLTNSQLTSGNQVLLDCILDLCQGKGHTKVSACRNAGGPYQPPLPHTLSAQVISLLGQLVVSCCWDLMRFSNGLCAGAAPRTESWMLSLFGGLRCSAKQGSKFLYVYTHCYKVTKYELSPLTSLILVPSPMQESFELFRHWRHNRLVNALSPGSLCANIQWVPTEDWQGLDVLRHQAVPVTRVAILEVIIWVNQVVDTRAPGRRSGFWGALSRWHLRVTMTYSPTVDRARRPTRTFRLTPAPPAPTIQFGTRGTKGLPFIFSLAVGRRGFRMSPPSNCKRIENTALLGNSKANGEMIVHWSRGERLFTTAYSGIGVRNPRLGRFWISIQFPPRKLHLEYPNQRHTRPWFTQERPLSRHSIIWGSRMTVHRSAPAPCLIRLLAVTIAMCSLRAWPRNYRRTVLAKAPYGSGSAGDGWSRTLAQVRWRGDVTPWRVKCSAPQLSILSNSTVCANAPTLRMLFNLRRMRHVLRKGDYSVNVTLCRAKKCKLSPGFWRRLCPVLQQKLPRRVPFPQNTVSRLQPAGCINVGWAEYIARGESWIKATIPYAELSWGTIAHPLSDRSVVPSVTAICMESRFIIPRWAVRHGFRNQFGGFSQTVLSDLLHPPALLLRDCRSANGQTFPGYFAGGARVPATAQPKFIRQCQTTNTSDLWPRAATCCSPHASSGRLQPFNILNDRLFGRLEVSAFNNLQKCACSYNPLWDEGSMLARLKQSKSCSCSPTASPTVAGKYISFSGHYSPRAVMLAYADWMTACPPRAWQKRINVAASRALSAESIVLDPDVTSDRVLSGYQIHNLRILCPVAVRTAGGDAFTVVGVNESHASHRHSCMAYLRNDWRYLVTTSQEVEAKTVMERHLHALTQDQSRPALQDYIDRIERNPLVSRVPGVGRVHAVYILSLHHGAPSNGAIQVTRLSFRWARHKKFSNSHPVFCLSARNGFPGVSPSNVISLLEAPVATYASLDDSLRRLLKSARLCVRSTCPAHQVSNITVLVEARDILVGPGESKTTSDRQFPPLRLQSLHSCHPTPGKVARFGLAKSTRVSSVRTCGSVLFQHEGHTKIPGCSWISCLVAPCTGSVVNRFQSFSRDRCSGYCLIPIRFLPASILCMLKAVRTLGCVQGAIHDRFAGFDGLKSGAPTPKGRYIRAIMAGCVETSFTLTQPLELLSGLMGCPCLVVDRMYDDISWTIHSLSTRHILMAVT'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 159
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eYGxvm9edvkb",
        "colab_type": "text"
      },
      "source": [
        "## Finding a Motif in DNA"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g4Q70I57dyXZ",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/subs/)\n",
        "\n",
        "\n",
        "Given two strings s and t, t is a substring of s if t is contained as a contiguous collection of symbols in s (as a result, t must be no longer than s).\n",
        "\n",
        "The position of a symbol in a string is the total number of symbols found to its left, including itself (e.g., the positions of all occurrences of 'U' in \"AUGCUUCAGAAAGGUCUUACG\" are 2, 5, 6, 15, 17, and 18). The symbol at position i of s is denoted by s[i].\n",
        "\n",
        "_**Note:** in Python we use 0-based numbering whereas this example is using 1-based numbering_\n",
        "\n",
        "A substring of s can be represented as s[j:k], where j and k represent the starting and ending positions of the substring in s; for example, if s = \"AUGCUUCAGAAAGGUCUUACG\", then s[2:5] = \"UGCU\".\n",
        "\n",
        "The location of a substring s[j:k] is its beginning position j; note that t will have multiple locations in s if it occurs more than once as a substring of s (see the Sample below).\n",
        "\n",
        "**Given:** Two DNA strings s and t (each of length at most 1 kbp).\n",
        "\n",
        "**Return:** All locations of t as a substring of s.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "GATATATGCATATACTT\n",
        "ATAT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "2 4 10\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rZKp4uThVq7a",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Kawn8XNxMWRE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_dna_motif(s,t):\n",
        "  \"\"\"\n",
        "  Find DNA Motif Locations\n",
        "\n",
        "  Given: two strings s and t (each of length <= 1kbp).\n",
        "  Return: all locations of t as a substring of s.\n",
        "  \"\"\"\n",
        "  sub_position = []\n",
        "  \n",
        "  for i in range(len(s)):\n",
        "   \n",
        "    if s[i:i+len(t)] == t:\n",
        "      sub_position.append(i+1)\n",
        "    \n",
        "  print(*sub_position)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3_fNXLpQfv-7",
        "colab_type": "code",
        "outputId": "9bb92996-0396-4ca8-9ba3-4b7f8bcd603e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        }
      },
      "source": [
        "# Sample Dataset\n",
        "get_dna_motif('GATATATGCATATACTT','ATAT')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n",
            "4\n",
            "10\n",
            "2 4 10\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "U8qqOkAkUyiU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test Dataset\n",
        "get_dna_motif('CGGATCTAAACGAGTTCTAAACATCTAAACAATTCTAAACCGGCTCTAAACGGTGTTCTAAACTCTAAACCGTCTAAACTCTAAACTCTAAACTAAGCTCTCTAAACTGTTTCTAAACGGAGGGTCTAAACGTCTAAACCTTCTAAACAATCTAAACTCTCTAAACCTCTAAACGTACTCTAAACTCTAAACTCTAAACTTCTAAACCTCTAAACGTAATCTAAACTATCTAAACTTTCTAAACGGTCTAAACGGCTACGCTTCTAAACTCTCTAAACTTGAAGATCTCTAAACTCTAAACTCTAAACTCTAAACATTCTAAACTTCTAAACTTCTAAACGCTGGATCTAAACACTTCTAAACATCTAAACTGATCGCTTCTAAACTTCTAAACTCTAAACTTCTAAACGCTCTAAACAACGAGAGTCTAAACACTCTAAACTCTAAACCATCTAAACAGGATTAACTTCTAAACTTCTAAACTCCTCTAAACATCTAAACTATGTCTAAACGCAATCTATCTAAACATCTAAACTCTAAACTCTAAACTCTAAACGATATTCTAAACCGATCTAAACAATCTAAACCTCTAAACCATCTAAACTCTAAACGTCTAAACGCCTTCTAAACTATCTAAACTCTAAACTAATCTCTAAACTCTAAACCTCTAAACTCTAAACGGCGTGGTCTAAACTCTAAACGTCTAAACTCTAAACCCTTCTAAACTCTAAACGAAATCTAAACCCGTCTAAACATCTAAACTCTAAACCCCCGAATCTAAACTCTAAACTAATCTAAACTCTAAACATCTAAACTTCTAAACTTCTAAACCAGCCCTCATAAAGGGCACTTAATCTAAACATCTAAACCATGTCTAAACGGGCGTCTAAACTGTTCTCCGTCTAAACTCTAAACGTACTGATTCTAAAC','TCTAAACTC')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "E8yoA2ZfXHi1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test Dataset - From File\n",
        "sequence,motif = open('rosalind_subs.txt').read().split()\n",
        "get_dna_motif(sequence,motif)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9YbrY4MEcnBp",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 2</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ae1oKfDJYdAP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_dna_motif2(s,t):\n",
        "  \"\"\"\n",
        "  Find DNA Motif Locations\n",
        "\n",
        "  Given: two strings s and t (each of length <= 1kbp).\n",
        "  Return: all locations of t as a substring of s.\n",
        "  \"\"\"\n",
        "  print(*[i+1 for i in range(len(s)) if s[i:i+len(t)] == t])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dqJ5-K7cZijy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Sample Dataset\n",
        "get_dna_motif2('GATATATGCATATACTT','ATAT')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cRHC1RVZdI0N",
        "colab_type": "text"
      },
      "source": [
        "## Consensus and Profile"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v8xTF1mfdV13",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/cons/)\n",
        "\n",
        "A matrix is a rectangular table of values divided into rows and columns. An m×n matrix has m rows and n columns. Given a matrix A, we write A<sub>i,j</sub> to indicate the value found at the intersection of row i and column j.\n",
        "\n",
        "Say that we have a collection of DNA strings, all having the same length n. Their profile matrix is a 4×n matrix P in which P<sub>1,j</sub> represents the number of times that 'A' occurs in the jth position of one of the strings, P<sub>2,j</sub> represents the number of times that C occurs in the jth position, and so on (see below).\n",
        "\n",
        "A consensus string c is a string of length n formed from our collection by taking the most common symbol at each position; the jth symbol of c therefore corresponds to the symbol having the maximum value in the j-th column of the profile matrix. Of course, there may be more than one most common symbol, leading to multiple possible consensus strings.\n",
        "\n",
        "**Given:** A collection of at most 10 DNA strings of equal length (at most 1 kbp) in FASTA format.\n",
        "\n",
        "**Return:** A consensus string and profile matrix for the collection. (If several possible consensus strings exist, then you may return any one of them.)\n",
        "\n",
        "**Sample Dataset:**\n",
        "\n",
        "\n",
        "```\n",
        ">Rosalind_1\n",
        "ATCCAGCT\n",
        ">Rosalind_2\n",
        "GGGCAACT\n",
        ">Rosalind_3\n",
        "ATGGATCT\n",
        ">Rosalind_4\n",
        "AAGCAACC\n",
        ">Rosalind_5\n",
        "TTGGAACT\n",
        ">Rosalind_6\n",
        "ATGCCATT\n",
        ">Rosalind_7\n",
        "ATGGCACT\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output:**\n",
        "\n",
        "\n",
        "```\n",
        "ATGCAACT\n",
        "A: 5 1 0 0 5 5 0 0\n",
        "C: 0 0 1 4 2 0 6 1\n",
        "G: 1 1 6 3 0 1 0 0\n",
        "T: 1 5 0 0 0 1 1 6\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Bj2_A9glptuX",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 1 - Biopython </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z_xyYc4_pj6o",
        "colab_type": "code",
        "outputId": "b4736c67-e801-40cd-d6ac-782917c5df3f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 139
        }
      },
      "source": [
        "# install BioPython (includes NumPy).\n",
        "!pip install biopython\n",
        "# import Bio SeqIO package from BioPython.\n",
        "from Bio import SeqIO"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting biopython\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/ed/77/de3ba8f3d3015455f5df859c082729198ee6732deaeb4b87b9cfbfbaafe3/biopython-1.74-cp36-cp36m-manylinux1_x86_64.whl (2.2MB)\n",
            "\u001b[K     |████████████████████████████████| 2.2MB 9.6MB/s \n",
            "\u001b[?25hRequirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from biopython) (1.16.5)\n",
            "Installing collected packages: biopython\n",
            "Successfully installed biopython-1.74\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ObM1Pe9CP_aO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# import NumPy\n",
        "import numpy as np\n",
        "# import Counter subclass from collections library.\n",
        "from collections import Counter"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "k6FTmvjTP_7V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def consensus_profile(fasta_file):\n",
        "  \"\"\"\n",
        "  Given: A collection of at <=10 DNA strings of equal length (at most 1 kbp) \n",
        "         in FASTA file format.\n",
        "  Return: A single consensus string, even if multiple exist, and profile matrix\n",
        "         for the collection.\n",
        "          \n",
        "  dna_matrix = a matrix where the rows are DNA strings and the columns are \n",
        "         relative nucleotide positions.\n",
        "  freq_matrix =\n",
        "  \"\"\"\n",
        "  dna_lists = []\n",
        "  consensus = \"\"\n",
        "  \n",
        "  with open(fasta_file, 'r') as infile:\n",
        "\n",
        "    for record in SeqIO.parse(infile, \"fasta\"):\n",
        "      dna_lists += [(record.seq)]\n",
        "  \n",
        "  # convert to sequence array.\n",
        "  dna_matrix = np.vstack(dna_lists)\n",
        " \n",
        "  # make iterable copy of dna matrix.\n",
        "  temp_matrix = zip(*dna_matrix)\n",
        "  \n",
        "  # count nucleotide frequencies and save as counter (dict subclass).\n",
        "  nuc_freq = np.array([Counter(col) for col in temp_matrix])\n",
        "  \n",
        "  # generate consensus sequence.\n",
        "  for counter in nuc_freq:\n",
        "    consensus += max(counter, key=counter.get)\n",
        "    \n",
        "  # generate profile matrix\n",
        "  profile_matrix = (np.array([[Counter(col).get(char,0) for char in 'ACGT']\n",
        "                   for col in nuc_freq]).T)\n",
        "    \n",
        "  print(consensus)\n",
        "  \n",
        "  for i,letter in enumerate('ACGT'):\n",
        "    print(f\"{letter}: {' '.join([str(count) for count in profile_matrix[i]])}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Xaii8EEJQGOd",
        "colab_type": "code",
        "outputId": "60605735-ec37-42af-f203-677acbbc460d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "# Sample Dataset - From File\n",
        "consensus_profile('rosalind_sample.fasta')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "ATGCAACT\n",
            "A: 5 1 0 0 5 5 0 0\n",
            "C: 0 0 1 4 2 0 6 1\n",
            "G: 1 1 6 3 0 1 0 0\n",
            "T: 1 5 0 0 0 1 1 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dNG-F6f1fQd5",
        "colab_type": "code",
        "outputId": "04e63309-eae7-4083-d85b-2b3d47711258",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 122
        }
      },
      "source": [
        "# Test Dataset - From File\n",
        "consensus_profile('rosalind_cons.txt')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "TCGGTTCTTCATATGTTCACCGAGGCCGACAACAGGTGGTAGTGCCTACTTCTGAGTGCTAGGAATCCATGGCAAGGCGCTTCGAGTCCCTTCCAGTTATTCTTGGTCAGTTCTGAAAACCAGCCTGGGTAGATTGTAGGTCACCGCTAATACAACACGGTCTTTTCGACGGTGCATCTCATTCAACCTCTCATACTCTGAGTCCCTAAATACAGAAGCTTAGGGTTTTTTACCCCTGCAACTCATGCTCGAGCTCAGTAAAGTAGTGGACGCTGAGCTGGACTCACCTGACTACCCATTCAACAATAAATAGGGGCGCAAGCTACGGCCGGTTCGCGCGGCTTAGAACCATCTTTTTAAGTCCGCTTGAGATCTTCCTGTTCGCGACCATGAGCTGCACCATACTTGTCTCTTTGGCCTGTGACCTAACTTAGATAGACACACTCTTTCCCGTGGTATCACCAGTTTAATACCTATGCTCCATGGCAGCCACCGGTAGCAGGAGGACGAATACAAATTCCGTGGAAGAACAATACAGAGGATTGGCTCATACAGCAGAGCTTGAATGTTGGGGATTAAACCACGATTCGCCCTCATATAGAATCTGCTACGGGATCTCTTAACGGATGGTATCTATTTAAGTACTGACATTAGTACACGGTGCACGGTGGTCCTGGGCAAGGGGGTGCCTGCTAGTCCGATAAGGTCCTGACGCGTCGAGTAATGATTCCCGGTAGGCGGGAGTAGTACAACTACAGAGTTGACGAAGAAAAGTATAGGCACTTGGCATGGCGTCGTACAATATGTGCCGTTTTGAACGAGACACGGCTTTTCACCTACACATCCAATACAAACGCTCTACCTTGCACGAGCTGAACGGTTAAGACCCCTTGACCATACTAGCGAACCTGA\n",
            "A: 3 2 2 1 2 3 2 2 0 4 4 3 5 2 1 2 1 1 3 3 1 1 4 3 3 0 1 2 4 3 5 6 4 4 2 0 1 2 3 3 5 0 0 3 2 2 1 6 2 3 0 0 3 3 3 2 1 3 3 2 3 1 1 5 4 3 1 1 5 3 1 3 3 4 4 2 2 1 3 1 4 3 3 2 4 3 2 3 3 3 1 2 3 2 5 4 2 2 5 1 1 2 2 2 3 1 0 1 4 2 0 4 4 2 2 5 4 3 4 2 3 3 3 1 3 0 2 2 0 2 4 1 4 3 2 3 3 4 3 1 3 3 3 2 3 2 0 0 3 4 2 4 3 3 4 1 5 3 2 3 1 2 3 3 2 2 1 2 4 0 4 1 2 3 1 5 2 2 3 2 4 0 4 1 4 4 2 1 1 2 1 1 4 1 5 3 2 2 0 0 4 2 3 3 2 3 1 3 4 4 0 4 2 4 0 5 3 3 2 1 2 4 1 3 2 0 2 3 2 2 1 4 2 2 2 2 1 2 3 4 3 0 1 2 4 1 2 2 3 3 3 5 2 3 2 2 6 2 2 4 6 5 3 0 4 3 2 1 3 4 3 2 2 2 2 4 3 2 2 1 2 4 2 3 1 5 1 4 4 2 3 4 1 4 2 1 2 3 3 2 4 3 4 2 5 4 0 4 3 5 2 5 0 2 2 2 3 0 0 4 5 2 2 2 5 1 2 1 1 3 3 3 2 0 2 3 0 2 1 1 4 1 2 0 5 2 5 4 1 2 4 2 2 2 3 0 1 3 5 4 2 2 3 1 2 2 2 3 3 4 2 4 2 1 0 3 2 3 2 2 1 2 2 0 2 2 5 2 2 3 2 3 5 0 2 3 2 1 6 3 2 5 2 5 1 2 2 2 3 1 1 4 3 3 2 4 2 1 2 1 1 1 2 5 1 3 2 4 5 3 3 1 5 3 4 1 3 3 3 3 4 1 5 3 3 2 2 3 3 1 2 2 3 3 3 1 2 5 2 2 4 1 1 5 3 3 4 3 5 3 1 4 2 1 1 4 3 3 1 1 2 2 4 2 3 1 2 3 3 1 3 4 1 2 2 0 2 4 2 2 4 3 1 4 3 2 5 2 3 4 3 0 6 4 4 4 4 1 3 3 4 1 1 1 0 5 4 3 3 4 2 4 3 3 4 2 4 3 3 2 2 4 3 2 2 2 1 3 2 4 3 4 2 6 3 1 6 2 4 2 2 1 2 2 4 6 2 2 4 1 0 2 1 1 3 4 2 4 4 4 4 3 3 0 2 4 1 0 3 3 4 0 2 2 2 4 2 4 3 4 3 5 3 0 3 1 1 0 2 5 2 2 1 1 5 2 2 2 2 2 2 5 4 2 2 3 3 3 1 0 3 5 3 2 1 5 4 2 1 4 4 2 2 4 1 3 4 4 1 3 3 2 5 3 2 6 2 3 2 2 0 3 3 3 5 2 0 2 2 0 2 1 2 2 0 2 3 1 3 4 3 2 3 3 2 3 3 2 1 2 3 3 2 3 4 1 2 1 3 3 5 2 5 4 1 3 2 2 2 4 2 3 1 3 1 1 1 3 2 3 0 3 4 4 2 1 3 3 3 2 2 2 2 2 0 4 2 4 1 2 1 2 6 2 0 6 1 2 3 1 6 4 1 3 3 4 6 2 4 0 0 3 2 3 2 3 6 3 3 4 4 5 5 0 3 5 2 5 4 0 2 4 3 3 2 2 1 2 4 1 3 2 1 2 2 2 3 2 5 3 3 4 2 3 1 1 1 1 0 0 1 5 4 2 0 3 3 4 4 2 3 2 5 4 4 3 1 3 1 1 3 2 3 2 5 2 1 1 3 1 5 2 3 1 0 0 4 4 2 5 2 5 4 4 3 1 2 3 3 3 3 2 3 3 2 1 3 3 1 2 4 1 0 0 2 4 6 3 1 1 2 2 4 5 2 4 2 3 2 3 2 2 2 6 0 2 5 4 5 3 1 3 2 2 2 4 3 3 0 2 2 5\n",
            "C: 3 5 1 2 1 1 6 2 3 4 3 2 3 3 3 2 3 4 3 3 5 4 2 2 0 5 5 3 2 3 2 1 4 1 2 2 1 2 1 1 1 3 3 0 4 4 3 0 3 2 2 6 1 3 3 2 2 2 3 2 2 2 2 1 1 2 5 5 4 1 3 2 4 2 3 2 0 4 1 4 2 1 3 3 1 2 1 5 3 3 2 2 3 4 1 0 1 3 0 2 2 6 1 2 1 1 1 4 2 2 4 1 4 1 2 2 2 3 2 4 3 2 1 4 3 4 0 1 2 3 1 2 1 1 3 3 2 3 1 3 0 3 2 3 4 3 5 4 3 3 2 2 4 3 2 3 2 4 3 0 2 5 2 2 2 1 4 3 1 5 1 1 1 0 4 2 1 4 2 7 0 3 2 5 2 1 4 4 3 7 2 3 1 2 1 3 1 3 3 2 2 1 0 4 4 5 2 3 1 3 3 1 4 1 3 2 2 0 4 3 0 2 3 1 1 1 3 0 2 3 3 2 5 4 4 4 3 1 4 3 2 6 0 3 2 2 2 3 3 6 2 0 3 3 3 5 2 3 3 1 0 2 2 3 2 2 2 3 0 2 4 3 3 3 3 1 1 5 3 0 3 4 4 1 5 2 5 5 2 1 2 4 3 1 3 4 3 2 1 1 4 2 2 4 0 2 2 1 3 3 2 0 2 2 2 2 4 2 4 1 2 1 3 3 1 4 1 3 5 4 2 1 3 3 4 1 5 2 3 3 1 3 1 2 1 1 1 4 4 4 2 2 4 2 3 3 2 3 3 3 1 1 4 5 2 3 2 1 2 1 1 2 2 4 3 3 4 3 3 4 2 3 4 3 4 2 0 6 4 3 3 1 2 2 5 0 3 4 2 5 4 4 1 0 6 1 3 2 2 3 2 4 3 1 2 1 1 4 4 3 2 2 3 1 4 3 3 3 3 3 0 1 2 2 0 2 3 2 3 4 1 4 2 3 3 3 0 1 3 4 5 4 2 2 1 0 3 1 1 3 4 5 4 3 2 1 1 2 2 3 3 3 3 4 3 1 2 1 5 1 3 3 1 3 1 3 4 1 1 5 4 2 4 5 2 2 2 2 2 4 1 3 2 3 3 4 1 3 0 1 3 2 2 4 3 3 2 2 2 3 4 3 2 3 3 1 1 1 3 1 4 3 2 2 2 4 2 0 2 2 2 0 2 2 2 2 6 0 3 2 2 2 4 2 3 4 1 3 2 2 4 3 3 2 2 1 1 2 2 1 3 2 1 1 2 0 2 3 1 2 5 5 3 5 2 2 2 1 5 3 4 6 4 2 5 3 1 3 0 2 2 0 3 3 4 2 1 5 2 3 4 2 3 2 2 2 4 1 4 1 2 0 3 3 3 0 3 0 3 2 1 1 3 4 2 2 2 3 1 1 3 3 2 2 5 1 2 2 5 2 2 1 3 2 1 2 5 1 4 1 3 2 2 3 2 4 3 2 1 3 1 2 4 4 2 2 2 3 5 4 2 2 1 2 1 2 3 2 4 4 3 3 5 0 3 4 1 5 3 3 3 1 1 1 2 1 2 4 4 2 1 2 4 2 4 0 3 4 1 2 2 1 2 3 3 1 2 3 2 4 3 6 2 1 4 2 1 1 5 3 2 2 1 0 3 1 3 4 3 5 2 1 6 3 3 4 2 1 3 4 3 1 2 2 4 1 1 2 1 3 2 1 3 3 2 1 3 2 0 1 3 3 3 2 2 3 1 5 2 3 1 2 4 1 0 5 1 2 2 5 2 1 2 1 1 3 3 2 5 4 3 0 1 3 2 1 3 2 4 2 3 3 4 4 3 4 2 1 4 1 3 2 1 4 1 4 4 0 2 4 2 4 3 1 4 5 2 1 1 2 4 2 3 1 3 2 3 0 4 1 1 5 3 1 3 2 3 2 4 3 2 1 5 1 1 1 2 4 3 2 3 1 3 1 2 3 4 4 3 3 2 1 1 2 5 3 3 0 1 4 2 2 2 3 2 3 2 3 4 2 2 0\n",
            "G: 1 0 4 4 2 3 2 2 3 1 0 2 2 0 5 2 3 2 1 1 2 5 2 3 5 2 3 3 2 3 1 2 0 3 5 5 2 4 4 2 3 4 3 7 2 2 1 3 2 1 3 3 2 3 1 3 3 4 2 2 2 5 6 0 2 2 2 2 1 3 3 3 0 1 0 4 6 1 5 2 0 2 2 3 2 4 2 1 2 2 3 3 1 3 1 4 3 2 3 2 3 1 3 3 4 6 4 2 1 4 2 1 1 2 5 2 2 1 2 2 2 2 5 2 2 2 5 4 5 1 2 4 3 2 2 4 1 1 4 3 2 2 3 2 0 3 4 1 2 1 1 1 3 2 1 3 3 1 4 4 2 2 1 2 1 2 3 5 3 3 4 5 3 4 3 1 3 1 1 1 3 2 0 0 3 2 2 3 3 0 3 3 3 1 2 3 2 2 3 6 0 5 3 2 3 1 3 2 3 1 2 3 2 1 4 2 2 5 2 3 3 3 4 4 5 4 2 2 2 2 1 2 3 3 3 3 2 5 1 2 2 3 3 3 2 2 4 3 0 1 3 2 5 2 1 1 1 3 1 2 1 2 5 3 0 4 2 4 5 3 2 4 3 1 4 3 4 2 1 5 5 2 2 1 1 2 2 0 0 4 3 2 1 3 2 2 2 2 0 3 1 2 1 2 2 2 4 3 2 1 0 2 5 3 5 4 1 4 3 2 1 4 3 2 3 3 6 4 3 2 3 4 1 3 1 4 1 4 3 4 4 3 3 3 2 4 1 1 3 2 1 1 1 3 1 3 3 1 2 1 6 3 2 3 4 3 3 2 3 2 5 2 2 2 1 0 2 1 1 4 3 2 3 5 2 3 3 2 3 1 0 5 0 5 1 3 3 2 1 2 0 0 0 3 3 3 2 3 1 3 3 0 0 1 3 5 4 2 3 2 4 3 4 0 3 3 1 2 1 2 2 2 1 3 3 3 2 4 2 1 3 3 1 2 1 2 3 2 1 3 1 3 3 1 4 5 1 2 3 2 1 3 2 1 3 1 0 2 2 1 2 0 2 2 3 3 2 5 1 3 2 2 3 1 4 3 1 3 5 1 2 2 4 1 4 5 2 1 3 2 3 3 4 1 3 4 3 2 4 4 1 2 1 1 2 2 3 2 2 3 0 5 3 5 4 3 1 4 1 2 2 1 3 2 3 1 2 5 2 4 4 3 0 2 4 4 2 3 2 3 1 2 2 0 3 2 3 5 2 4 2 1 2 4 1 2 2 3 0 3 4 3 5 4 2 0 3 2 3 0 1 0 2 1 3 1 0 3 1 3 1 1 2 1 0 2 3 1 1 3 3 3 1 3 2 1 4 2 3 0 2 4 5 5 2 2 1 3 3 3 1 4 2 2 3 4 1 3 3 4 1 2 1 4 3 1 0 2 2 2 3 4 3 2 1 2 4 2 4 2 2 3 1 3 1 1 1 3 2 6 4 2 3 3 2 3 5 5 3 4 6 2 2 2 4 3 3 5 0 2 3 3 4 4 4 4 0 3 2 3 1 4 2 3 2 5 3 2 2 4 1 3 3 4 4 4 1 3 1 0 6 2 2 3 2 7 2 1 5 3 6 0 2 0 2 6 2 0 1 2 2 1 4 5 1 2 6 4 2 3 5 5 1 5 3 2 4 0 2 4 1 3 2 0 1 1 2 4 2 5 2 2 3 3 2 4 1 2 3 1 3 2 0 4 2 3 1 0 5 6 2 2 3 2 2 4 6 2 3 2 4 5 3 4 4 2 4 2 2 0 3 3 1 3 3 3 2 5 3 3 4 0 1 1 4 5 1 3 2 4 2 4 0 1 1 2 5 4 1 3 0 0 2 2 2 3 3 3 3 1 0 4 2 3 3 2 2 3 2 1 2 1 1 2 2 5 3 2 1 1 3 2 3 3 1 5 1 3 1 3 2 7 2 4 4 3 0 0 4 4 2 3 2 2 4 1 2 0 3 3 3 3 5 1 4 3 0 2 1 1 2 2 6 3 3 3 2 3 3 2 4 3\n",
            "T: 3 3 3 3 5 3 0 4 4 1 3 3 0 5 1 4 3 3 3 3 2 0 2 2 2 3 1 2 2 1 2 1 2 2 1 3 6 2 2 4 1 3 4 0 2 2 5 1 3 4 5 1 4 1 3 3 4 1 2 4 3 2 1 4 3 3 2 2 0 3 3 2 3 3 3 2 2 4 1 3 4 4 2 2 3 1 5 1 2 2 4 3 3 1 3 2 4 3 2 5 4 1 4 3 2 2 5 3 3 2 4 4 1 5 1 1 2 3 2 2 2 3 1 3 2 4 3 3 3 4 3 3 2 4 3 0 4 2 2 3 5 2 2 3 3 2 1 5 2 2 5 3 0 2 3 3 0 2 1 3 5 1 4 3 5 5 2 0 2 2 1 3 4 3 2 2 4 3 4 0 3 5 4 4 1 3 2 2 3 1 4 3 2 6 2 1 5 3 4 2 4 2 4 1 1 1 4 2 2 2 5 2 2 4 3 1 3 2 2 3 5 1 2 2 2 5 3 5 4 3 5 2 0 1 1 1 4 2 2 1 3 1 6 2 2 5 2 2 4 0 2 3 0 2 4 2 1 2 4 3 3 1 0 4 4 1 4 2 2 1 1 1 2 4 1 2 2 1 4 4 0 0 2 5 3 1 2 1 4 3 2 0 5 2 3 3 3 3 6 4 1 3 3 2 3 2 4 2 2 1 6 3 3 3 1 2 2 4 3 3 2 3 2 3 1 2 1 2 1 1 2 2 4 4 3 2 4 2 3 2 1 3 4 5 2 3 3 1 2 2 3 5 3 3 3 4 4 3 0 2 1 4 1 1 2 2 3 4 2 3 2 2 4 3 6 4 2 3 4 0 4 3 1 2 2 3 2 0 1 3 5 1 3 3 2 4 2 3 1 0 4 1 7 2 0 4 3 3 4 3 4 2 4 5 3 0 3 3 1 4 3 4 1 4 2 1 4 1 1 2 5 6 2 2 3 4 2 1 2 2 2 2 2 2 3 3 5 4 3 2 2 1 2 4 2 4 4 2 4 3 1 1 3 1 2 5 5 3 1 3 4 3 3 3 3 2 3 1 3 5 3 3 2 4 2 3 3 3 1 3 1 2 1 2 2 3 4 3 3 2 2 1 3 2 1 0 1 3 3 1 3 6 1 1 1 1 1 5 3 1 2 1 4 1 3 1 4 2 3 3 2 2 2 3 1 3 2 2 3 2 2 3 5 4 2 2 1 4 3 1 4 2 2 2 1 3 0 0 2 2 2 5 3 2 3 1 5 3 4 5 3 3 3 4 3 6 3 1 2 4 0 2 2 4 3 3 7 6 1 1 1 3 2 5 3 1 4 2 6 1 2 2 3 4 1 6 4 3 3 2 2 2 1 2 1 4 3 4 1 4 5 1 1 3 2 3 3 4 3 4 5 2 3 0 4 2 4 3 6 3 0 1 3 2 3 4 0 2 0 3 3 4 1 2 6 1 2 3 2 1 3 3 2 1 1 1 2 1 4 3 1 5 2 2 4 3 2 1 2 0 2 3 2 1 3 1 4 3 3 1 3 0 1 4 1 0 4 2 2 0 1 4 1 1 3 2 5 1 3 4 1 3 3 2 3 2 4 2 2 2 2 6 2 3 3 2 3 4 4 2 3 1 2 2 5 2 1 1 2 2 2 1 2 3 4 1 2 4 2 0 1 2 1 4 3 1 0 3 1 1 5 4 3 2 2 2 2 3 3 2 1 2 2 3 3 1 4 3 1 3 3 1 1 3 4 1 2 1 1 4 2 1 2 3 4 1 2 4 1 2 2 2 5 3 5 3 4 2 2 3 2 5 4 4 4 1 3 1 0 2 2 1 1 1 2 1 2 2 4 5 4 6 4 2 2 1 2 6 2 4 3 0 2 5 3 3 2 2 5 2 2 2 2 3 2 2 2 5 2 5 3 1 1 3 4 2 3 2 4 2 2 1 3 5 3 2 2 3 2 3 3 4 1 2 2 2 2 3 2 1 3 4 2 1 1 2 2 4 3 2 5 3 0 2 3 0 3 1 3 4 2 2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "50MQ1fFmfs2l",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 2 - Biopython (by Glen)</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z0dSg5htfvqY",
        "colab_type": "code",
        "outputId": "595897ba-7344-4abb-ce9e-b51abb77811b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "# Read FASTA to a np array\n",
        "sequence_array = np.array([record.seq for record in SeqIO.parse('rosalind_sample.fasta','fasta')])\n",
        "\n",
        "# generate counters for each column of the sequence array\n",
        "counters = [Counter(column) for column in sequence_array.T]\n",
        "\n",
        "# generate the profile matrix\n",
        "profile_matrix = np.array([[counter.get(char,0) for char in \"ACGT\"] for counter in counters])\n",
        "\n",
        "print(\"\".join([counter.most_common(1)[0][0] for counter in counters]))\n",
        "for i,letter in enumerate(\"ACGT\"):\n",
        "  print(f\"{letter}: {' '.join([str(count) for count in profile_matrix.T[i]])}\")"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "ATGCAACT\n",
            "A: 5 1 0 0 5 5 0 0\n",
            "C: 0 0 1 4 2 0 6 1\n",
            "G: 1 1 6 3 0 1 0 0\n",
            "T: 1 5 0 0 0 1 1 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xDmEp2ZCGyJH",
        "colab_type": "text"
      },
      "source": [
        "## Mortal Fibonacci Rabbits"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Yjp-Q2X-G6WP",
        "colab_type": "text"
      },
      "source": [
        "**[Problem](http://rosalind.info/problems/fibd/)**\n",
        "\n",
        "Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2 and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month.\n",
        "\n",
        "Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).\n",
        "\n",
        "**Given:** Positive integers n≤100 and m≤20.\n",
        "\n",
        "**Return:** The total number of pairs of rabbits that will remain after the n-th month if all rabbits live for m months.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "6 3\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "4\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YUxwAZZi_Fgm",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1<h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6zwIPnz5HZ-F",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mortal_rabbits(n,m):\n",
        "  \"\"\"\n",
        "  Given: Positive integers n (<=100) and m (<=20).\n",
        "  Return: The total number of pairs of rabbits that will remain after the n-th \n",
        "          month if all rabbits live for m months and are only able to reproduce\n",
        "          after the first month (to reach maturity).\n",
        "\n",
        "  n = number of months.\n",
        "  m = number of months all rabbits live.\n",
        "  \"\"\"\n",
        "  \n",
        "  # starting pair and potential offspring pairs.\n",
        "  # list stores how many pairs are alive and at what age.\n",
        "  # e.g. if m = 3; [0] = 1 month, [1] = 2 months, [2] = 3 months\n",
        "  pairs = [1] + [0]*(m-1)\n",
        "\n",
        "  # iterate over total months, excluding starting month shown above.\n",
        "  for month in range(n-1):\n",
        "    # number of rabbit pairs each month; new offspring from existing adults \n",
        "    # plus number of rabbit pairs that have not died (i.e. exclude last index).\n",
        "     pairs = [sum(pairs[1:])] + pairs[:-1]\n",
        "\n",
        "  # total number of surviving rabbit pairs.\n",
        "  return(sum(pairs))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FWzADfK92U9u",
        "colab_type": "code",
        "outputId": "72a9b7cf-968a-4360-b5c3-39051d18fa43",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Sample Dataset\n",
        "mortal_rabbits(6,3)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 32
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3t32r7Rf3GlW",
        "colab_type": "code",
        "outputId": "7f2f8f78-ffa4-46ba-b54a-54e4ce6cce86",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Test Dataset\n",
        "mortal_rabbits(94,17)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "19546080223167369637"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 33
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZT8EsiDy6DzA",
        "colab_type": "text"
      },
      "source": [
        "## Calculating Expected Offspring"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "73_bz8x66GgN",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/iev/)\n",
        "\n",
        "For a random variable X taking integer values between 1 and n, the expected value of X is E(X)=∑nk=1k×Pr(X=k). The expected value offers us a way of taking the long-term average of a random variable over a large number of trials.\n",
        "\n",
        "As a motivating example, let X be the number on a six-sided die. Over a large number of rolls, we should expect to obtain an average of 3.5 on the die (even though it's not possible to roll a 3.5). The formula for expected value confirms that E(X)=∑6k=1k×Pr(X=k)=3.5.\n",
        "\n",
        "More generally, a random variable for which every one of a number of equally spaced outcomes has the same probability is called a uniform random variable (in the die example, this \"equal spacing\" is equal to 1). We can generalize our die example to find that if X is a uniform random variable with minimum possible value a and maximum possible value b, then E(X)=a+b2. You may also wish to verify that for the dice example, if Y is the random variable associated with the outcome of a second die roll, then E(X+Y)=7.\n",
        "\n",
        "**Given:** Six nonnegative integers, each of which does not exceed 20,000. The integers correspond to the number of couples in a population possessing each genotype pairing for a given factor. In order, the six given integers represent the number of couples having the following genotypes:\n",
        "\n",
        "AA-AA\n",
        "AA-Aa\n",
        "AA-aa\n",
        "Aa-Aa\n",
        "Aa-aa\n",
        "aa-aa\n",
        "\n",
        "**Return:** The expected number of offspring displaying the dominant phenotype in the next generation, under the assumption that every couple has exactly two offspring.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        "1 0 0 1 0 1\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "3.5\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cfYbOgf-_CDO",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 1</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hF3xiE1zL4AD",
        "colab_type": "code",
        "outputId": "2e560a5e-9e69-466b-8d93-87a11c70134b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def expected_offspring(given):\n",
        "  \"\"\"\n",
        "  Given: Six non-negative integers (each <=20,000) as a string. The integers \n",
        "         correspond to the number of couples in a population possessing each \n",
        "         genotype pairing for a given factor. In order, the six given integers \n",
        "         represent the number of couples having the following genotypes:\n",
        "\n",
        "         AA-AA AA-Aa AA-aa Aa-Aa Aa-aa aa-aa\n",
        "\n",
        "  Return: The expected number of offspring displaying the dominant phenotype in \n",
        "          the next generation, under the assumption that every couple has \n",
        "          exactly two offspring.\n",
        "\n",
        "  \"\"\"\n",
        "  # punnet square non-dominant factor probabilities.\n",
        "    # AA-AA = 0\n",
        "    # AA-Aa = 0\n",
        "    # AA-aa = 0\n",
        "    # Aa-Aa = 0.25\n",
        "    # Aa-aa = 0.5\n",
        "    # aa-aa = 1\n",
        "\n",
        "  dataset = list(map(int, given.split()))\n",
        "  total_adults = sum(dataset)\n",
        "\n",
        "  # determine probabiliy of offspring with recessive phenotype.\n",
        "  rec_prob = ((dataset[3]*0.25) + (dataset[4]*0.5) + dataset[5]) / total_adults\n",
        "\n",
        "  # return probability of offspring with dominant phenotype multiplied by\n",
        "  # the number of offspring.\n",
        "  return round(((1 - rec_prob)*total_adults*2),1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10000000 loops, best of 3: 55.6 ns per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "crJj0oDRbJko",
        "colab_type": "code",
        "outputId": "32a57e08-5b8f-4480-ee04-3c173e40a07d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Sample Dataset\n",
        "expected_offspring('1 0 0 1 0 1')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3.5"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 78
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cucwQIahbV0e",
        "colab_type": "code",
        "outputId": "fc9d08a5-6ca5-49fa-e83c-609e0addbf7f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Test Dataset\n",
        "expected_offspring('19024 18068 16651 19205 16761 17082')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "153054.5"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 79
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MSkjkb7Mb4iK",
        "colab_type": "text"
      },
      "source": [
        "<h4>Version 2 (by Sharno)</h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BCsDT4TGb7-H",
        "colab_type": "code",
        "outputId": "a69b7cf4-34bb-4b56-aba7-b6ef0e71462e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def expected_offspring2(given):\n",
        "  \"\"\"\n",
        "  Given: Six non-negative integers (each <=20,000) as a string. The integers \n",
        "         correspond to the number of couples in a population possessing each \n",
        "         genotype pairing for a given factor. In order, the six given integers \n",
        "         represent the number of couples having the following genotypes:\n",
        "\n",
        "         AA-AA AA-Aa AA-aa Aa-Aa Aa-aa aa-aa\n",
        "\n",
        "  Return: The expected number of offspring displaying the dominant phenotype in \n",
        "          the next generation, under the assumption that every couple has \n",
        "          exactly two offspring.\n",
        "\n",
        "  \"\"\"\n",
        "  \n",
        "  return sum([a*int(b) for a,b in zip([2,2,2,1.5,1,0], given.split())])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10000000 loops, best of 3: 54.5 ns per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R-p2jU5qdR_1",
        "colab_type": "text"
      },
      "source": [
        "## Overlap Graphs"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MP23YIqLdUS1",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/grph/)\n",
        "\n",
        "A graph whose nodes have all been labeled can be represented by an adjacency list, in which each row of the list contains the two node labels corresponding to a unique edge.\n",
        "\n",
        "A directed graph (or digraph) is a graph containing directed edges, each of which has an orientation. That is, a directed edge is represented by an arrow instead of a line segment; the starting and ending nodes of an edge form its tail and head, respectively. The directed edge with tail v and head w is represented by (v,w) (but not by (w,v)). A directed loop is a directed edge of the form (v,v).\n",
        "\n",
        "For a collection of strings and a positive integer k, the overlap graph for the strings is a directed graph Ok in which each string is represented by a node, and string s is connected to string t with a directed edge when there is a length k suffix of s that matches a length k prefix of t, as long as s≠t; we demand s≠t to prevent directed loops in the overlap graph (although directed cycles may be present).\n",
        "\n",
        "**Given:** A collection of DNA strings in FASTA format having total length at most 10 kbp.\n",
        "\n",
        "**Return:** The adjacency list corresponding to O3. You may return edges in any order.\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        ">Rosalind_0498\n",
        "AAATAAA\n",
        ">Rosalind_2391\n",
        "AAATTTT\n",
        ">Rosalind_2323\n",
        "TTTTCCC\n",
        ">Rosalind_0442\n",
        "AAATCCC\n",
        ">Rosalind_5013\n",
        "GGGTGGG\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Ouput**\n",
        "\n",
        "\n",
        "```\n",
        "Rosalind_0498 Rosalind_2391\n",
        "Rosalind_0498 Rosalind_0442\n",
        "Rosalind_2391 Rosalind_2323\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "T9bMcy9HcsAp",
        "colab_type": "text"
      },
      "source": [
        "## Finding a Shared Motif"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Xgqnxb9AcuW_",
        "colab_type": "text"
      },
      "source": [
        "[Problem](http://rosalind.info/problems/lcsm/)\n",
        "\n",
        "A common substring of a collection of strings is a substring of every member of the collection. We say that a common substring is a longest common substring if there does not exist a longer common substring. For example, \"CG\" is a common substring of \"ACGTACGT\" and \"AACCGTATA\", but it is not as long as possible; in this case, \"CGTA\" is a longest common substring of \"ACGTACGT\" and \"AACCGTATA\".\n",
        "\n",
        "Note that the longest common substring is not necessarily unique; for a simple example, \"AA\" and \"CC\" are both longest common substrings of \"AACC\" and \"CCAA\".\n",
        "\n",
        "**Given:** A collection of k (k≤100) DNA strings of length at most 1 kbp each in FASTA format.\n",
        "\n",
        "**Return:** A longest common substring of the collection. (If multiple solutions exist, you may return any single solution.)\n",
        "\n",
        "**Sample Dataset**\n",
        "\n",
        "\n",
        "```\n",
        ">Rosalind_1\n",
        "GATTACA\n",
        ">Rosalind_2\n",
        "TAGACCA\n",
        ">Rosalind_3\n",
        "ATACA\n",
        "```\n",
        "\n",
        "\n",
        "**Sample Output**\n",
        "\n",
        "\n",
        "```\n",
        "AC\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZFHtfGtgc7eG",
        "colab_type": "text"
      },
      "source": [
        "<h4> Version 1 </h4>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yMyrLU6vc-EF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}