Week3-2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "# Input:  A list of strings Dna, and integers k and t\n",
    "# Output: RandomMotifs(Dna, k, t)\n",
    "# HINT:   You might not actually need to use t since t = len(Dna), but you may find it convenient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Count(Motifs):\n",
    "    count = {} # initializing the count dictionary\n",
    "    k = len(Motifs[0])\n",
    "    for symbol in \"ACGT\":\n",
    "        count[symbol] = []\n",
    "        for j in range(k):\n",
    "            count[symbol].append(0)\n",
    "\n",
    "    t = len(Motifs)\n",
    "    for i in range(t):\n",
    "        for j in range(k):\n",
    "            symbol = Motifs[i][j]\n",
    "            count[symbol][j] += 1\n",
    "    return count\n",
    "\n",
    "\n",
    "\n",
    "def Profile(Motifs):\n",
    "    count = {} # initializing the count dictionary\n",
    "    profile = {}\n",
    "    k = len(Motifs[0])\n",
    "    for symbol in \"ACGT\":\n",
    "        count[symbol] = []\n",
    "        for j in range(k):\n",
    "            count[symbol].append(0)\n",
    "\n",
    "    t = len(Motifs)\n",
    "    for i in range(t):\n",
    "        for j in range(k):\n",
    "            symbol = Motifs[i][j]\n",
    "            count[symbol][j] += 1\n",
    "    ## divide the number of motif strings to get frequency\n",
    "    for letter in count.keys():\n",
    "        profile[letter] = [x/ float(t) for x in count[letter]]\n",
    "    return profile\n",
    "\n",
    "def Consensus(Motifs):\n",
    "    k = len(Motifs[0])\n",
    "    count = Count(Motifs)\n",
    "    consensus = \"\"\n",
    "    for j in range(k):\n",
    "        m = 0\n",
    "        frequentSymbol = \"\"\n",
    "        for symbol in \"ACGT\":\n",
    "            if count[symbol][j] > m:\n",
    "                m = count[symbol][j]\n",
    "                frequentSymbol = symbol\n",
    "        consensus += frequentSymbol\n",
    "    return consensus\n",
    "\n",
    "def Score(Motifs):\n",
    "    consensus = Consensus(Motifs)\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    score = 0\n",
    "    for i in range(k):\n",
    "        FrequentSymbol = consensus[i]\n",
    "        for j in range(t):\n",
    "            if Motifs[j][i] != FrequentSymbol:\n",
    "                score = score + 1\n",
    "    return score\n",
    "\n",
    "# Input:  String Text and profile matrix Profile\n",
    "# Output: Pr(Text, Profile)\n",
    "def Pr(Text, Profile):\n",
    "    p = 1\n",
    "    for i in range(len(Text)):\n",
    "        p = p * Profile[Text[i]][i]\n",
    "    return p\n",
    "\n",
    "def ProfileMostProbablePattern(Text, k, Profile):\n",
    "    p_dict = {}\n",
    "    for i in range(len(Text)- k +1):\n",
    "        p = Pr(Text[i: i+k], Profile)\n",
    "        p_dict[i] = p\n",
    "    m = max(p_dict.values())\n",
    "    keys = [k for k,v in p_dict.items() if v == m]\n",
    "    ind = keys[0]\n",
    "    return Text[ind: ind +k]\n",
    "\n",
    "\n",
    "def GreedyMotifSearch(Dna, k, t):\n",
    "    BestMotifs = []\n",
    "    for i in range(0, t):\n",
    "        BestMotifs.append(Dna[i][0:k])\n",
    "    n = len(Dna[0])\n",
    "    for i in range(n-k+1):\n",
    "        Motifs = []\n",
    "        Motifs.append(Dna[0][i:i+k])\n",
    "        for j in range(1, t):\n",
    "            P = Profile(Motifs[0:j])\n",
    "            Motifs.append(ProfileMostProbablePattern(Dna[j], k, P))\n",
    "        if Score(Motifs) < Score(BestMotifs):\n",
    "            BestMotifs = Motifs\n",
    "    return BestMotifs\n",
    "\n",
    "\n",
    "def CountWithPseudocounts(Motifs):\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    count = {}\n",
    "    for symbol in \"ACGT\":\n",
    "        count[symbol] = []\n",
    "        for j in range(k):\n",
    "            count[symbol].append(1)\n",
    "    for i in range(t):\n",
    "        for j in range(k):\n",
    "            symbol = Motifs[i][j]\n",
    "            count[symbol][j] += 1\n",
    "    return count\n",
    "\n",
    "def ProfileWithPseudocounts(Motifs):\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    count = CountWithPseudocounts(Motifs)\n",
    "    profile= {}\n",
    "    ## divide the number of motif strings to get frequency\n",
    "    for letter in count.keys():\n",
    "        profile[letter] = [float(x)/ (t+4) for x in count[letter]]\n",
    "    return profile\n",
    "\n",
    "\n",
    "def GreedyMotifSearchWithPseudocounts(Dna, k, t):\n",
    "    BestMotifs = []\n",
    "    for i in range(0, t):\n",
    "        BestMotifs.append(Dna[i][0:k])\n",
    "    n = len(Dna[0])\n",
    "    for i in range(n-k+1):\n",
    "        Motifs = []\n",
    "        Motifs.append(Dna[0][i:i+k])\n",
    "        for j in range(1, t):\n",
    "            P = ProfileWithPseudocounts(Motifs[0:j])\n",
    "            Motifs.append(ProfileMostProbablePattern(Dna[j], k, P))\n",
    "        if Score(Motifs) < Score(BestMotifs):\n",
    "            BestMotifs = Motifs\n",
    "    return BestMotifs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Motifs(Profile, Dna):\n",
    "    motifs = []\n",
    "    t = len(Dna)\n",
    "    #k = 4\n",
    "    for i in range(t):\n",
    "        motif = ProfileMostProbablePattern(Dna[i], k, Profile)\n",
    "        motifs.append(motif)\n",
    "    return motifs\n",
    "\n",
    "def RandomMotifs(Dna, k, t):\n",
    "    # place your code here.\n",
    "    motifs= []\n",
    "    for i in range(t):\n",
    "        ind = random.randint(0, len(Dna[0])-k)\n",
    "        motif = Dna[i][ind:ind +k]\n",
    "        motifs.append(motif)\n",
    "    return motifs\n",
    "\n",
    "def RandomizedMotifSearch(Dna, k, t):\n",
    "    M = RandomMotifs(Dna, k, t)\n",
    "    BestMotifs = M\n",
    "    while True:\n",
    "        Profile = ProfileWithPseudocounts(M)\n",
    "        M = Motifs(Profile, Dna)\n",
    "        if Score(M) < Score(BestMotifs):\n",
    "            BestMotifs = M\n",
    "        else:\n",
    "            return BestMotifs "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CGCCCCTCTCGGGGGTGTTCAGTAAACGGCCA GGGCGAGGTATGTGTAAGTGCCAAGGTGCCAG TAGTACCGAGACCGAAAGAAGTATACAGGCGT TAGATCAAGTTTCAGGTGCACGTCGGTGAACC AATCCACCAGCTCCACGTGCAATGTTGGCCTA\n",
      "TCAGTAAA AGGTGCCA AAGAAGTA TCAAGTTT ATCCACCA\n"
     ]
    }
   ],
   "source": [
    "dna = list(input().split())\n",
    "k = 8\n",
    "t = 5\n",
    "zz = RandomMotifs(dna, k, t)\n",
    "print(*zz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "# Input:  A list of strings Dna, and integers k and t\n",
    "# Output: RandomMotifs(Dna, k, t)\n",
    "# HINT:   You might not actually need to use t since t = len(Dna), but you may find it convenient\n",
    "def RandomMotifs(Dna, k, t):\n",
    "    # place your code here.\n",
    "    motifs= []\n",
    "    for i in range(t):\n",
    "        ind = random.randint(0, len(Dna[0])-k)\n",
    "        motif = Dna[i][ind:ind +k]\n",
    "        motifs.append(motif)\n",
    "    return motifs\n",
    "\n",
    "def RandomizedMotifSearch(Dna, k, t):\n",
    "    M = RandomMotifs(Dna, k, t)\n",
    "    BestMotifs = M\n",
    "    while True:\n",
    "        Profile = ProfileWithPseudocounts(M)\n",
    "        M = Motifs(Profile, Dna)\n",
    "        if Score(M) < Score(BestMotifs):\n",
    "            BestMotifs = M\n",
    "        else:\n",
    "            return BestMotifs \n",
    "\n",
    "def ProfileWithPseudocounts(Motifs):\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    count = CountWithPseudocounts(Motifs)\n",
    "    profile= {}\n",
    "    ## divide the number of motif strings to get frequency\n",
    "    for letter in count.keys():\n",
    "        profile[letter] = [float(x)/ (t+4) for x in count[letter]]\n",
    "    return profile\n",
    "\n",
    "def CountWithPseudocounts(Motifs):\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    count = {}\n",
    "    for symbol in \"ACGT\":\n",
    "        count[symbol] = []\n",
    "        for j in range(k):\n",
    "            count[symbol].append(1)\n",
    "    for i in range(t):\n",
    "        for j in range(k):\n",
    "            symbol = Motifs[i][j]\n",
    "            count[symbol][j] += 1\n",
    "    return count\n",
    "# Insert necessary subroutines here, including RandomMotifs(), ProfileWithPseudocounts(), Motifs(), Score(),\n",
    "# and any subroutines that these functions need.\n",
    "def Pr(Text, Profile):\n",
    "    p = 1\n",
    "    for i in range(len(Text)):\n",
    "        p = p * Profile[Text[i]][i]\n",
    "    return p\n",
    "\n",
    "def ProfileMostProbablePattern(Text, k, Profile):\n",
    "    p_dict = {}\n",
    "    for i in range(len(Text)- k +1):\n",
    "        p = Pr(Text[i: i+k], Profile)\n",
    "        p_dict[i] = p\n",
    "    m = max(p_dict.values())\n",
    "    keys = [k for k,v in p_dict.items() if v == m]\n",
    "    ind = keys[0]\n",
    "    return Text[ind: ind +k]\n",
    "\n",
    "def Consensus(Motifs):\n",
    "    k = len(Motifs[0])\n",
    "    count = CountWithPseudocounts(Motifs)\n",
    "    consensus = \"\"\n",
    "    for j in range(k):\n",
    "        m = 0\n",
    "        frequentSymbol = \"\"\n",
    "        for symbol in \"ACGT\":\n",
    "            if count[symbol][j] > m:\n",
    "                m = count[symbol][j]\n",
    "                frequentSymbol = symbol\n",
    "        consensus += frequentSymbol\n",
    "    return consensus\n",
    "\n",
    "def Score(Motifs):\n",
    "    consensus = Consensus(Motifs)\n",
    "    t = len(Motifs)\n",
    "    k = len(Motifs[0])\n",
    "    score = 0\n",
    "    for i in range(k):\n",
    "        FrequentSymbol = consensus[i]\n",
    "        for j in range(t):\n",
    "            if Motifs[j][i] != FrequentSymbol:\n",
    "                score = score + 1\n",
    "    return score\n",
    "### DO NOT MODIFY THE CODE BELOW THIS LINE ###\n",
    "def RepeatedRandomizedMotifSearch(Dna, k, t):\n",
    "    BestScore = float('inf')\n",
    "    BestMotifs = []\n",
    "    for i in range(1000):\n",
    "        Motifs = RandomizedMotifSearch(Dna, k, t)\n",
    "        CurrScore = Score(Motifs)\n",
    "        if CurrScore < BestScore:\n",
    "            BestScore = CurrScore\n",
    "            BestMotifs = Motifs\n",
    "    return BestMotifs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TGCTCCCCCTATCGG TGCCTGACCAAGAAA TGCACGTACAAGAAA TGCACCTTGAAGAAA TGCAATTCCAAGAAA TGCGAAACCAAGAAA GGCACCACCAAGACC TGCACCACCGCTAAA TGCACCACACCGAAA TGCACTCTCAAGAAA TGCACCACCAATTCA TGCACCACCACCCAA CTCACCACCAAGAAT TGCATGGCCAAGAAA TGTGACACCAAGAAA TGCACCGTGAAGAAA TGCACCACCAAGCGC ATGACCACCAAGAAA TGCACCAAGTAGAAA TATTCCACCAAGAAA\n"
     ]
    }
   ],
   "source": [
    "dna = [\n",
    "    'TTTCCCGCCGACCTAGTTACAGAGGTACCAGAGGGCAGCTACTTAGGGGGCCTCCCGCATCACTGAACCTTTATATAGCCTAGTAGGATCGGCCCACTTAGCCTGAGTCCGGACTTTACTCGTGGATGACCTGCTCCCCCTATCGGCATACAGTTGTAAGCCTTAGTCTTTCCCGCCGACCTA',\n",
    "    'GTTACAGAGGTACCAGAGGGCAGCTACTTAGGGGGCCTCCCGCATCACTGTGCCTGACCAAGAAAAACCTTTATATAGCCTAGTAGGATCGGCCCACTTAGCCTGAGTCCGGACTTTACTCGTGGATGACCTGCTCCCCCTATCGGCATACAGTTGTAAGCCTTAGTCTTTCCCGCCGACCTA',\n",
    "    'TGCAAACTTGTAAGTCAACGCGATCGACTCCAAATTTGCCCACGCATATACAGCGGCATGCCCCAAATATTAGGCATGCTACTTTATTAATCGTCGGAGCTTACTAGGAGAGCGCTAGCTAAAGCTGCGTCTGATGTTCTATATCTCGACAGTTCAGGCAACTGCACGTACAAGAAAATAGGT',\n",
    "    'AACACTCGCTGTCGACAATTCGCGGACCCAGAATTCAAGGTAGCCGATGACGGGCCTTACGAAAAAAAGCGCTGAAGGGGTGGGGAGTTCAATTAGCCACTGAAAATTTTTTTTTTTGCACCTTGAAGAAACGATGGGGTTGAGAACCGTACAGAAGCCGTATTACGCTTGACGTGTTAATCG',\n",
    "    'GATTCTGAGGTCGACCATGAGCGATAATGCCAAGTCGTGCAATTCCAAGAAATGATGGAGAATCCCGGGCCCGTGTGATTCCTTTACGGGTGCGTGCCCGAACGTCTATAAACTCCGACTGGCCACAATGAATGATAGCCGCGTATAGGGAGCGCGTGTCTCTACAAAACATATGAACATGAA',\n",
    "    'TAATACCTTTGCGAAACCAAGAAAAGACGGTCCGCCGAAGTTAGATGGAGAGCAGCACCTCACTCTTCAATATAAGGCCGAGCCCACTACCCGTAGTTGACCTCAGTTAGATCCTCTGGTCAAAAATCTAGTCCGAATCGATTCAACTTCTCGACCTCAATGCCTTACCGGGAGATAATTCAC',\n",
    "    'CACTTGAAGAGCGGGCTCCAAACCTCCGTGTTCCTGGCAATTTAGTCTAAGTCCGAATATGACTATTGTAGTCAGATCGCCCGAGCGCGGCGAATGACGAATTTTGGCCGCGTAATTCCCGGACAGCGAGTGCGTCCAAACACACCCAGAGGGCACCACCAAGACCTCAATATGGATGTGACT',\n",
    "    'TTGCACCACCGCTAAACCCACTCGACATTGTGTGTCGACCGTGGAAACCGCTACATACTACTAAGGGTTCACTTTGTAGGGTCAACGGCGAGCAACAATGTATATTTGGACACCGCACCCCATAGGTTTGATCGTGATCCGGACATTGTAATTTCAACTCTATCTCGGATCTGCAGTACGATC',\n",
    "    'ACGGTTCACGTACGTCCGGTAACCTCCCCCGGGTGACAGAATGGTTGGTTTACGCTATGAGGACGAAGTTCTCCCCCTCTTATGGCATTTGTAGGTCCTCCGTCGGTACTTTCTACGTGCCCCAATGCCTCCTCTGGGCTATGCCAAAGGCGGTGCACCACACCGAAAGGTTTGATTAAGACA',\n",
    "    'TTCTCATACTGCCACCAAACTGTGAGTGAGCGGTGAGTTTACCCGCGACCTAAGAGTCCTGTTGTTTGAATGTCTGCACTCTCAAGAAACGGCATTACGTTTCGTCACCTGGGCAACTTAAATGGAAATTGCTACGTTTTGAGCAACGGGATAATCCCCAACTCCCACCTCCGCGAGCCTAAC',\n",
    "    'CCCCCAAATTAAGTTTTGAGTGCACCACCAATTCAACTGATCACGAGCTCGAAGCGGATCCATACAACTGTGGAGTGTGCGCAGAGGATGCCCTTCAACTCAGACGGGAAAGGCACGACACGGGCACGGATATATAAAGACATGTCCATCCGTAATACGTCAGTATTAGACGATCATTCAAGC',\n",
    "    'AGACGACCTGGGTGCCCTAGAGTAGGCTGCGATGCCCACCTTATCTTCGGATATTGGATGTGAATATCGGCCGTCCGGGTAGCGAGTAAACCGTGAACACTGAAGTACTGCCGATCAATCAGAACGAATTGCACCACCACCCAACTAACAGCTTCTACCCGTATGCCTCATACGAGCCCTCTT',\n",
    "    'GAACTGAACTCATTTTAAGGTTAAACTTAAACTTTTAGGAATGAGTCTCATACGGCAAACAGACGAAGCGATACCCTGAGACCTACTTATGAAGCGTCCTCCCGCGCTCGGTTACAGTAATCCTGGGGAGGGAACGCTACCCTCTCTCACCACCAAGAATATAACTAACCGCGTACGGGCGGG',\n",
    "    'CGATGGATGTAAGTCATGTTTCACTTCGCCCGCATGGTTTGGCTTCCTTATTCAACGATGCAGGAAACTTGTGCTGGATACGACACCGTGCATGGCCAAGAAAGGACAGTTGTGTGTTCCTTTCCCCACCTTCTAGCACGCAGCTTCTGGGCGTGTATTAGGCATATGCGACGAATACGGAGT',\n",
    "    'TTTAGATCGAGACAATTGAAGCCAAAGCAAGGTCATGGATGGTATCCCTCCTCCGACACCCAGATGCGAGTGAGTGGGTTAGCTCTCTTAAGTGTGACACCAAGAAATGGCAAGGTATTGTCTTATGATAGTGCACTGATGTTCCGGTAACGATTTTAGATGGAACGTCACACGACGGTACAG',\n",
    "    'CATGTACCTGCTGGCGCGCGCCTATACTATAGCTTTGAGCAACAACAGCAGCTGATCGCGACAGCCTGTAGCGTCGCGTTATATCAGATGCGGTTATCGAGTCGACGCAACCACCCTACATGAAAGCTCTGAGCTTGCACCGTGAAGAAAGGGTACCTTCCTCTAGAACCCTAGTATTAACGC',\n",
    "    'AGACTTATAGGGCGACATCATGCCACTGAGCTTGCAGTCTAGACCATATTAGAGACGACGCTACGTCCCTTGCACCACCAAGCGCATCAAGTTGGGGTCGCTACCATCATACAAGGTCCTATGCGCGGTGGGTGAACATTTATGGAAAGCTTAATCGTTGCGAAGGGAAATGCTGCAGTAGAT',\n",
    "    'TCGCGGTGTGCGCTTGCATGTTCTCATACTCTGCATTTAGCTACCAAGATGAACCACTTAGTAACTCCGTACCCCGGATGATGTATACTCCGATCCTAGCGACGACGACGTACACACGGGTATTCATCATGACCACCAAGAAAAGCTCCGATCGAGTCGAGGACATGACATAAATCGCCCGCC',\n",
    "    'AACGATGGTGATCTTCTTATTCCAAGGAATTCCTCGCGGTGCACCAAGTAGAAAAGCAATAATATGAAGTTACTGGAAATGATTGACCCCCGCATACATTGCCGGGCATGGGATGTATAATCTAAAACCTTGCGGCAGTTTTACGAACCGCTGCGCACAGTACGCCTAGGACTCCAATATCCC',\n",
    "    'GCGTCCCGCTTGATCATTTCTCACGGTATTCCACCAAGAAACTTCCCTGCCCTTCGCTTAGGGCACCGAACGTTGAGTGTCCTCGGCATTATTTTTCATGGCTTGGCCTGTCGAAAAGAAGCCAAGCTACGACTGGCGGTACGACGCATGATGGCTAAACGGTCATAGACCGTGATGCTGGAA'\n",
    "]\n",
    "k = 15\n",
    "t = 20\n",
    "zz = RepeatedRandomizedMotifSearch(dna, k, t)\n",
    "print(*zz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}