{
 "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": true
   },
   "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": true
   },
   "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=\"161pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 161.00 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 157,-256 157,4 -4,4\"/>\n",
       "<!-- GC -->\n",
       "<g id=\"node1\" class=\"node\"><title>GC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">GC</text>\n",
       "</g>\n",
       "<!-- CG -->\n",
       "<g id=\"node4\" class=\"node\"><title>CG</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">CG</text>\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=\"M48.1601,-216.411C47.2975,-208.507 47.0481,-198.852 47.4119,-189.935\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"50.9033,-190.179 48.1206,-179.956 43.9209,-189.683 50.9033,-190.179\"/>\n",
       "</g>\n",
       "<!-- AC -->\n",
       "<g id=\"node2\" class=\"node\"><title>AC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" 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=\"M111.43,-218.834C101.25,-208.938 87.4761,-195.546 75.9694,-184.359\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.4055,-181.846 68.7957,-177.385 73.5259,-186.865 78.4055,-181.846\"/>\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",
       "<!-- TC -->\n",
       "<g id=\"node5\" class=\"node\"><title>TC</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">TC</text>\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=\"M33.3986,-72.411C36.5136,-64.3352 40.3337,-54.4312 43.8346,-45.3547\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"47.1265,-46.5458 47.4597,-35.9562 40.5955,-44.0267 47.1265,-46.5458\"/>\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=\"M59.8794,-179.956C60.7139,-187.827 60.9485,-197.374 60.5831,-206.187\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.0742,-206.184 59.8399,-216.411 64.0558,-206.691 57.0742,-206.184\"/>\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=\"M47.6014,-144.411C44.4864,-136.335 40.6663,-126.431 37.1654,-117.355\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"40.4045,-116.027 33.5403,-107.956 33.8735,-118.546 40.4045,-116.027\"/>\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=\"M57.6538,-36.0925C59.6758,-46.4315 61.9808,-59.9098 63,-72 64.3441,-87.9434 64.3441,-92.0566 63,-108 62.2834,-116.501 60.9311,-125.688 59.4884,-133.988\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"56.0309,-133.438 57.6538,-143.908 62.9142,-134.711 56.0309,-133.438\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%dotstr visualize_de_bruijn(\"ACGCGTCG\", 3)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}