4.03_DeBruijn.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def de_bruijn_ize(st, k):\n",
    "    \"\"\" Return a list holding, for each k-mer, its left\n",
    "        k-1-mer and its right k-1-mer in a pair \"\"\"\n",
    "    edges = []\n",
    "    nodes = set()\n",
    "    for i in range(len(st) - k + 1):\n",
    "        edges.append((st[i:i+k-1], st[i+1:i+k]))\n",
    "        nodes.add(st[i:i+k-1])\n",
    "        nodes.add(st[i+1:i+k])\n",
    "    return nodes, edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nodes, edges = de_bruijn_ize(\"ACGCGTCG\", 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AC', 'CG', 'GC', 'GT', 'TC'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('AC', 'CG'),\n",
       " ('CG', 'GC'),\n",
       " ('GC', 'CG'),\n",
       " ('CG', 'GT'),\n",
       " ('GT', 'TC'),\n",
       " ('TC', 'CG')]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def visualize_de_bruijn(st, k):\n",
    "    \"\"\" Visualize a directed multigraph using graphviz \"\"\"\n",
    "    nodes, edges = de_bruijn_ize(st, k)\n",
    "    dot_str = 'digraph \"DeBruijn graph\" {\\n'\n",
    "    for node in nodes:\n",
    "        dot_str += '  %s [label=\"%s\"] ;\\n' % (node, node)\n",
    "    for src, dst in edges:\n",
    "        dot_str += '  %s -> %s ;\\n' % (src, dst)\n",
    "    return dot_str + '}\\n'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# might have to do this first:\n",
    "# %install_ext https://raw.github.com/cjdrake/ipython-magic/master/gvmagic.py\n",
    "%load_ext gvmagic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n",
       " -->\n",
       "<!-- Title: DeBruijn graph Pages: 1 -->\n",
       "<svg width=\"147pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 146.93 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>DeBruijn graph</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 142.934,-256 142.934,4 -4,4\"/>\n",
       "<!-- CG -->\n",
       "<g id=\"node1\" class=\"node\"><title>CG</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">CG</text>\n",
       "</g>\n",
       "<!-- GT -->\n",
       "<g id=\"node3\" class=\"node\"><title>GT</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">GT</text>\n",
       "</g>\n",
       "<!-- CG&#45;&gt;GT -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>CG&#45;&gt;GT</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M84.4297,-146.834C74.2501,-136.938 60.4761,-123.546 48.9694,-112.359\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"51.4055,-109.846 41.7957,-105.385 46.5259,-114.865 51.4055,-109.846\"/>\n",
       "</g>\n",
       "<!-- GC -->\n",
       "<g id=\"node4\" class=\"node\"><title>GC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">GC</text>\n",
       "</g>\n",
       "<!-- CG&#45;&gt;GC -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>CG&#45;&gt;GC</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M93.1601,-144.411C92.2975,-136.507 92.0481,-126.852 92.4119,-117.935\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"95.9033,-118.179 93.1206,-107.956 88.9209,-117.683 95.9033,-118.179\"/>\n",
       "</g>\n",
       "<!-- TC -->\n",
       "<g id=\"node2\" class=\"node\"><title>TC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">TC</text>\n",
       "</g>\n",
       "<!-- TC&#45;&gt;CG -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>TC&#45;&gt;CG</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106.208,-32.4344C116.629,-42.1841 129.257,-56.3637 135,-72 140.516,-87.0191 139.703,-92.7067 135,-108 131.714,-118.685 125.46,-129.149 119.075,-137.919\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"116.116,-136.023 112.75,-146.069 121.646,-140.314 116.116,-136.023\"/>\n",
       "</g>\n",
       "<!-- GT&#45;&gt;TC -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>GT&#45;&gt;TC</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M40.3607,-74.1548C48.8803,-64.6885 60.0854,-52.2384 69.6935,-41.5628\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.5704,-43.5982 76.6586,-33.8238 67.3674,-38.9154 72.5704,-43.5982\"/>\n",
       "</g>\n",
       "<!-- GC&#45;&gt;CG -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>GC&#45;&gt;CG</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.879,-107.956C105.714,-115.827 105.948,-125.374 105.583,-134.187\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"102.074,-134.184 104.84,-144.411 109.056,-134.691 102.074,-134.184\"/>\n",
       "</g>\n",
       "<!-- AC -->\n",
       "<g id=\"node5\" class=\"node\"><title>AC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">AC</text>\n",
       "</g>\n",
       "<!-- AC&#45;&gt;CG -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>AC&#45;&gt;CG</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M99,-215.697C99,-207.983 99,-198.712 99,-190.112\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-190.104 99,-180.104 95.5001,-190.104 102.5,-190.104\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%dotstr visualize_de_bruijn(\"ACGCGTCG\", 3)"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}