Week8_Indexing_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 8 - Indexing "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lab you'll implement some methods for genome indexing: hash tables and tries.\n",
    "\n",
    "Note that since we're using algorithms that are of size $O(m^2)$ (suffix tries rather than suffix trees), and representing tries with high-level data structures, we won't fit realistic genome sizes into memory. However we should achieve fast lookup."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you want to be able to draw the tries, you need the graphviz package. If using your own computer, you may need to install the graphviz package with either\n",
    "\n",
    "    conda install -c conda-forge python-graphviz\n",
    "    \n",
    "or\n",
    "\n",
    "    pip install graphviz\n",
    "    \n",
    "Using `pip` will probably require you to have the graphviz command-line tool already installed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "import itertools\n",
    "import graphviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import skbio"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from trie_utilities import draw_trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings in lectures:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "text1 = \"CGTGCGTGCTT\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "text2 = \"GTTATAGCTGATCGCGGCGTAGCGG\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first 1000 base-pairs of the viral genome, phiX:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import with skbio and convert to just a string\n",
    "phiX = str(skbio.DNA.read('data/phi-X174-1000bp.fa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Or read it ourselves, assuming a file with one FASTA record\n",
    "with open('data/phi-X174-1000bp.fa') as f:\n",
    "    _identifier_row = f.readline()\n",
    "    # Read the rest of the lines and join them into one string\n",
    "    phiX = ''.join([row.strip() for row in f.readlines()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generators and iterators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're going to introduce a new kind of Python object - generators - in order to generate large number of strings without occupying a lot of memory.\n",
    "\n",
    "You already know that we can iterate over lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in [1,3,5]:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also iterate over other data types, like sets and dicts. Any type we can iterate over is *iterable*.\n",
    "\n",
    "*Generators* and *iterators* are special kinds of Python object that are iterable, but which don't need to store any contents in memory. Instead they calculate each value on request.\n",
    "\n",
    "(A generator is a particular kind of iterator, but for this tutorial we are not going to worry about the difference between them.)\n",
    "\n",
    "We can make an example iterator using `iter()` on a data structure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "number_iterator = iter([1,3,5])\n",
    "print(number_iterator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can iterate over this just like the original list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in number_iterator:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The built-in `next()` function gets the next value from an iterator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "number_iterator = iter([1,3,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(number_iterator)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(number_iterator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What do you think would happen if we ran our `for` loop now, i.e. tried to iterate with \n",
    "\n",
    "`for x in number_iterator` ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in number_iterator:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More usefully, we can create a generator using a generator function. This means we never need to store all the objects in memory. A generator function is easy to recognise as it uses the `yield` keyword rather than the `return` keyword to return values.\n",
    "\n",
    "Here's a (normal) function that returns a list of k-mers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_kmers_list(text, k):\n",
    "    ''' \n",
    "    Return a list of all k-mers of length k from string t.\n",
    "    K-mers may be non-unique.\n",
    "    '''\n",
    "    result = []\n",
    "    for i in range(len(text)-k+1):\n",
    "        kmer = text[i:i+k]\n",
    "        result.append(kmer)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "get_kmers_list('BANANA', 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a *generator function* that returns all the k-mers in the string, but only calculates each one as it is asked for. Every time the function reaches the `yield` keyword, it makes a new value available, which is consumed by whatever we are using to iterate, such as a `for` loop. At no point do we need to store the whole list of k-mers in memory!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_kmers_iterator(text, k):\n",
    "    ''' \n",
    "    Return a generator yielding all k-mers of length k from string t.\n",
    "    K-mers may be non-unique.\n",
    "    '''\n",
    "    result = []\n",
    "    for i in range(len(text)-k+1):\n",
    "        kmer = text[i:i+k]\n",
    "        yield kmer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice we yield the kmers one at a time. We don't try to return the whole list at once. There is no list!\n",
    "\n",
    "Every time `next()` is called on our generator, either by a `for` loop or some other means, the function resumes running from where it left off and runs until it gets to a `yield` statement.\n",
    "\n",
    "This gives us a generator, which is iterable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for kmer in get_kmers_iterator('BANANA',3):\n",
    "    print(kmer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# There is no list\n",
    "print(get_kmers_iterator('BANANA', 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can still assign the generator to a variable (if we want to)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmers = get_kmers_iterator('BANANA', 3)\n",
    "print(kmers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unlike with a list, Python can't tell us how many k-mers are going to be returned in total, as it hasn't built a list - it doesn't know what any of the k-mers are yet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(kmers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(kmers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for kmer in kmers:\n",
    "    print(kmer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This concept is very useful if we want to iterate over large number of k-mers or suffixes and store them in a more concise data structure, and don't want to hold them all in memory in the meantime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The itertools module provides lots of handy iterators, and ways to create them. E.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "yesno_forever = itertools.cycle(['yes', 'no'])\n",
    "count = 0\n",
    "for x in yesno_forever:\n",
    "    print(x)\n",
    "    count += 1\n",
    "    if count > 5:\n",
    "        # This gets us out of the for loop\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`enumerate()` can also work with iterators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmers = get_kmers_iterator('BANANA', 3)\n",
    "for (i, kmer) in enumerate(kmers):\n",
    "    print(i, kmer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kmer index via hash table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1:**\n",
    "\n",
    "Write a function which, given a text string and a value k, builds a k-mer index using a Python dict as a hash table. The keys of the dictionary should be the unique k-mers, and the values should be lists of positions in the text string where the k-mer can be found. \n",
    "\n",
    "Note that you don't need to worry about collisions - the `dict` type takes care of all the details of the hash table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kmer_index(text, k):\n",
    "    ''' \n",
    "    Given a text string and integer k, build a dict of lists representing\n",
    "    a k-mer index.\n",
    "    '''\n",
    "    index = defaultdict(list)\n",
    "    for (i,kmer) in enumerate(get_kmers_iterator(text, k)):\n",
    "        index[kmer].append(i)\n",
    "    # return a dict rather than a defaultdict\n",
    "    return dict(index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'BA': [0], 'AN': [1, 4], 'ND': [2], 'DA': [3], 'NA': [5]}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# {'BA': [0], 'AN': [1, 4], 'ND': [2], 'DA': [3], 'NA': [5]}\n",
    "kmer_index('BANDANA', 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'CGTGC': [0, 4],\n",
       " 'GTGCG': [1],\n",
       " 'TGCGT': [2],\n",
       " 'GCGTG': [3],\n",
       " 'GTGCT': [5],\n",
       " 'TGCTT': [6]}"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmer_index(text1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "phiX_index = kmer_index(phiX, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "838"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How many kmers in index?\n",
    "# The smaller value we use for k, the less unique kmers we expect\n",
    "len(phiX_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['GAGTTT', 'AGTTTT', 'GTTTTA', 'TTTTAT', 'TTTATC']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(phiX_index.keys())[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 614]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phiX_index['GAGTTT']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suffixes "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2:**\n",
    "\n",
    "Write a generator function `suffixes()` which, given a genome text, returns all tuples of the form `(i, suffix)` where `i` is a position in the genome text and `suffix` is the corresponding suffix string. Remember to append \"$\" to the text!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def suffixes(text):\n",
    "    ''' \n",
    "    Given a text string, yield all suffixes and their genomic positions as tuples\n",
    "    of the form (position, suffix)\n",
    "    '''\n",
    "    text += '$'\n",
    "    for i in range(len(text)):\n",
    "        yield (i, text[i:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Should return\n",
    "```\n",
    "(0, 'BANANA$')\n",
    "(1, 'ANANA$')\n",
    "(2, 'NANA$')\n",
    "(3, 'ANA$')\n",
    "(4, 'NA$')\n",
    "(5, 'A$')\n",
    "(6, '$')\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0, (0, 'BANANA$')\n",
      "(1, 'ANANA$')\n",
      "(2, 'NANA$')\n",
      "(3, 'ANA$')\n",
      "(4, 'NA$')\n",
      "(5, 'A$')\n",
      "(6, '$')\n"
     ]
    }
   ],
   "source": [
    "for s in suffixes('BANANA'):\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suffix tries "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're going to build tries that are intended to be used as suffix tries. We'll represent them as nested dictionaries. \n",
    "\n",
    "Any node will be represented by a dict where the dict keys are characters labelling the edges, and the dict values are the child nodes.\n",
    "\n",
    "Since this is a suffix trie, the genomic indices we're looking up are only ever stored at leaf nodes, and the edge leading to a leaf node is always labelled with '$'. So we'll represent a leaf node and its incoming edge with a dict that looks like\n",
    "\n",
    "```{'$':23}```\n",
    "\n",
    "where the value in this leaf node represents the genomic coordinate we want to look up. \n",
    "\n",
    "Notice that we're only storing one integer value per leaf - this is fine for suffixes. Because of this, and because we've assumed the '$' character, we'd need a slightly different data structure for a k-mer trie index or for tries storing generic strings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example trie storing only one string, 'A$', with value 6:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "example_trie1 = {'A': {'$': 6}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "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: Suffix trie Pages: 1 -->\n",
       "<svg width=\"44pt\" height=\"216pt\"\n",
       " viewBox=\"0.00 0.00 44.00 216.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 212)\">\n",
       "<title>Suffix trie</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-212 40,-212 40,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-171.595C18,-160.257 18,-145.227 18,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-132.095 18,-122.095 14.5001,-132.095 21.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"24.4224\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> A</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-85.5951C18,-74.2572 18,-59.2271 18,-46.3153\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-46.0951 18,-36.0952 14.5001,-46.0952 21.5001,-46.0951\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x113612668>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_trie(example_trie1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example trie storing suffixes and index values `'AN$':6` and `'AAN$':5` (of course this cannot be a complete suffix trie - it only has two of the suffixes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# nested-dict representation of trie that stores strings with values \n",
    "# 'AN$':[2,6] and 'AAN$':[5]\n",
    "example_trie2 = {'A':{\n",
    "                    'N': {'$': 6}, \n",
    "                    'A': {'N': {'$': 5}}\n",
    "                    }\n",
    "                }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': {'N': {'$': 6}, 'A': {'N': {'$': 5}}}}"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_trie2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "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: Suffix trie Pages: 1 -->\n",
       "<svg width=\"98pt\" height=\"388pt\"\n",
       " viewBox=\"0.00 0.00 98.00 388.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 384)\">\n",
       "<title>Suffix trie</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-384 94,-384 94,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"46\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"46\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M46,-343.595C46,-332.257 46,-317.227 46,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"49.5001,-304.095 46,-294.095 42.5001,-304.095 49.5001,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"52.4224\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> A</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M40.6013,-258.804C36.6756,-247.027 31.2767,-230.83 26.7401,-217.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"29.9604,-215.813 23.4776,-207.433 23.3196,-218.027 29.9604,-215.813\"/>\n",
       "<text text-anchor=\"middle\" x=\"40.8052\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> N</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M51.1368,-258.404C54.769,-246.669 59.7132,-230.696 63.8768,-217.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"67.2605,-218.149 66.8739,-207.561 60.5735,-216.079 67.2605,-218.149\"/>\n",
       "<text text-anchor=\"middle\" x=\"66.4224\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> A</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-171.595C18,-160.257 18,-145.227 18,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-132.095 18,-122.095 14.5001,-132.095 21.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-171.595C72,-160.257 72,-145.227 72,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-132.095 72,-122.095 68.5001,-132.095 75.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"78.8052\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> N</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-85.5951C72,-74.2572 72,-59.2271 72,-46.3153\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-46.0951 72,-36.0952 68.5001,-46.0952 75.5001,-46.0951\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x113612390>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_trie(example_trie2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3:**\n",
    "\n",
    "Write a function which takes a trie, a string and an integer value, and adds the string to the trie, adding the value at the resulting leaf node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_string(trie, keystring, value):\n",
    "    '''\n",
    "    Given a dict representing a trie, a key string, and an integer value,\n",
    "    add the key string to the trie and add the value at the leaf node.\n",
    "    The key string must be of at least length 1 and end with '$'.\n",
    "    '''\n",
    "    node = trie\n",
    "    # Add all but the last character\n",
    "    for char in keystring[:-1]:\n",
    "        if char not in node:\n",
    "            node[char] = {}\n",
    "        node = node[char]\n",
    "    # The last character must be a '$'\n",
    "    assert keystring[-1]=='$'\n",
    "    # Add the final node with key '$' and the given value\n",
    "    node['$'] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'b': {'a': {'$': 0}}, '$': 2}, 'b': {'a': {'$': 1}}, '$': 3}"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Should return\n",
    "# {'a': {'b': {'a': {'$': 0}}, '$': 2}, 'b': {'a': {'$': 1}}, '$': 3}\n",
    "\n",
    "# An empty trie is just an empty dict\n",
    "aba_trie = dict()\n",
    "add_string(aba_trie, 'aba$',0)\n",
    "add_string(aba_trie, 'ba$',1)\n",
    "add_string(aba_trie, 'a$',2)\n",
    "add_string(aba_trie, '$',3)\n",
    "aba_trie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "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: Suffix trie Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"388pt\"\n",
       " viewBox=\"0.00 0.00 206.00 388.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 384)\">\n",
       "<title>Suffix trie</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-384 202,-384 202,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M116.594,-346.368C108.386,-333.601 96.3361,-314.856 86.8308,-300.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"89.65,-297.983 81.2983,-291.464 83.7618,-301.768 89.65,-297.983\"/>\n",
       "<text text-anchor=\"middle\" x=\"107.857\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>0&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126,-343.595C126,-332.257 126,-317.227 126,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.5,-304.095 126,-294.095 122.5,-304.095 129.5,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"131.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> b</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\"><title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"180\" y=\"-271.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>0&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M135.406,-346.368C143.614,-333.601 155.664,-314.856 165.169,-300.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"168.238,-301.768 170.702,-291.464 162.35,-297.983 168.238,-301.768\"/>\n",
       "<text text-anchor=\"middle\" x=\"162.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.5939,-260.368C54.3861,-247.601 42.3361,-228.856 32.8308,-214.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"35.65,-211.983 27.2983,-205.464 29.7618,-215.768 35.65,-211.983\"/>\n",
       "<text text-anchor=\"middle\" x=\"54.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> b</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-185.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>1&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-257.595C72,-246.257 72,-231.227 72,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-218.095 72,-208.095 68.5001,-218.095 75.5001,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-171.595C18,-160.257 18,-145.227 18,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-132.095 18,-122.095 14.5001,-132.095 21.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.8569\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-85.5951C18,-74.2572 18,-59.2271 18,-46.3153\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-46.0951 18,-36.0952 14.5001,-46.0952 21.5001,-46.0951\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126,-257.595C126,-246.257 126,-231.227 126,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.5,-218.095 126,-208.095 122.5,-218.095 129.5,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"130.857\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126,-171.595C126,-160.257 126,-145.227 126,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.5,-132.095 126,-122.095 122.5,-132.095 129.5,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"131.25\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1a108e6518>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_trie(aba_trie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'n': {'a': {'n': {'a': {'$': 1}}, '$': 3}}, '$': 5}, '$': 6}"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_trie = dict()\n",
    "add_string(test_trie, 'anana$',1)\n",
    "add_string(test_trie, 'ana$',3)\n",
    "add_string(test_trie, 'a$',5)\n",
    "add_string(test_trie, '$',6)\n",
    "# We haven't added all the suffixes, but this trie will still work for display\n",
    "# should return {'a': {'n': {'a': {'n': {'a': {'$': 1}}, '$': 3}}, '$': 5}, '$': 6}\n",
    "test_trie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Only top-level edges are 'a' and '$'\n",
    "len(test_trie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4:**\n",
    "\n",
    "Use your `suffixes()` generator function and your `add_string()` function to build a suffix trie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def suffix_trie(text):\n",
    "    ''' \n",
    "    Given a text string, return the suffix trie.\n",
    "    '''\n",
    "    trie = dict()\n",
    "    for (pos, suffix) in suffixes(text):\n",
    "        add_string(trie, suffix, pos)\n",
    "    return trie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'b': {'a': {'$': 0}}, '$': 2}, 'b': {'a': {'$': 1}}, '$': 3}"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# {'a': {'b': {'a': {'$': 0}}, '$': 2}, 'b': {'a': {'$': 1}}, '$': 3}\n",
    "suffix_trie('aba')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'b': {'a': {'n': {'a': {'n': {'a': {'$': 0}}}}}},\n",
       " 'a': {'n': {'a': {'n': {'a': {'$': 1}}, '$': 3}}, '$': 5},\n",
       " 'n': {'a': {'n': {'a': {'$': 2}}, '$': 4}},\n",
       " '$': 6}"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "suffix_trie('banana')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "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: Suffix trie Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"646pt\"\n",
       " viewBox=\"0.00 0.00 260.00 646.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 642)\">\n",
       "<title>Suffix trie</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-642 256,-642 256,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"130\" cy=\"-620\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"37\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M117.069,-607.32C101.747,-593.481 76.0143,-570.239 57.8629,-553.844\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"59.8883,-550.957 50.1212,-546.851 55.1963,-556.152 59.8883,-550.957\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> b</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"104\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>0&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M124.863,-602.404C121.231,-590.669 116.287,-574.696 112.123,-561.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"115.427,-560.079 109.126,-551.561 108.739,-562.149 115.427,-560.079\"/>\n",
       "<text text-anchor=\"middle\" x=\"123.857\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\"><title>16</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"158\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\"><title>0&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M135.399,-602.804C139.324,-591.027 144.723,-574.83 149.26,-561.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"152.68,-562.027 152.522,-551.433 146.04,-559.813 152.68,-562.027\"/>\n",
       "<text text-anchor=\"middle\" x=\"151.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node23\" class=\"node\"><title>22</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"212\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212\" y=\"-529.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;22 -->\n",
       "<g id=\"edge22\" class=\"edge\"><title>0&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M142.099,-606.606C155.423,-592.957 177.03,-570.823 192.699,-554.772\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"195.37,-557.046 199.851,-547.445 190.361,-552.156 195.37,-557.046\"/>\n",
       "<text text-anchor=\"middle\" x=\"181.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.1551,-516.001C30.5369,-504.426 27.0177,-488.868 24.0296,-475.657\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.3944,-474.668 21.7744,-465.687 20.5669,-476.212 27.3944,-474.668\"/>\n",
       "<text text-anchor=\"middle\" x=\"33.8569\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-429.595C18,-418.257 18,-403.227 18,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-390.095 18,-380.095 14.5001,-390.095 21.5001,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-343.595C18,-332.257 18,-317.227 18,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-304.095 18,-294.095 14.5001,-304.095 21.5001,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.8569\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-257.595C18,-246.257 18,-231.227 18,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-218.095 18,-208.095 14.5001,-218.095 21.5001,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-171.595C18,-160.257 18,-145.227 18,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-132.095 18,-122.095 14.5001,-132.095 21.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.8569\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-85.5951C18,-74.2572 18,-59.2271 18,-46.3153\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-46.0951 18,-36.0952 14.5001,-46.0952 21.5001,-46.0951\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\"><title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M97.8301,-516.804C93.2703,-504.835 86.9716,-488.3 81.7356,-474.556\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"84.9817,-473.245 78.151,-465.146 78.4403,-475.737 84.9817,-473.245\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.25\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\"><title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-443.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\"><title>8&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.346,-516.404C111.42,-504.669 115.603,-488.696 119.127,-475.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"122.515,-476.122 121.663,-465.561 115.743,-474.348 122.515,-476.122\"/>\n",
       "<text text-anchor=\"middle\" x=\"122.25\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\"><title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-429.595C72,-418.257 72,-403.227 72,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-390.095 72,-380.095 68.5001,-390.095 75.5001,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"76.8569\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\"><title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\"><title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-343.595C72,-332.257 72,-317.227 72,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-304.095 72,-294.095 68.5001,-304.095 75.5001,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\"><title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-271.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\"><title>10&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.4061,-346.368C89.6139,-333.601 101.664,-314.856 111.169,-300.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"114.238,-301.768 116.702,-291.464 108.35,-297.983 114.238,-301.768\"/>\n",
       "<text text-anchor=\"middle\" x=\"108.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\"><title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\"><title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-257.595C72,-246.257 72,-231.227 72,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-218.095 72,-208.095 68.5001,-218.095 75.5001,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"76.8569\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\"><title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\"><title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-171.595C72,-160.257 72,-145.227 72,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-132.095 72,-122.095 68.5001,-132.095 75.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node18\" class=\"node\"><title>17</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\"><title>16&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.346,-516.404C165.42,-504.669 169.603,-488.696 173.127,-475.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"176.515,-476.122 175.663,-465.561 169.743,-474.348 176.515,-476.122\"/>\n",
       "<text text-anchor=\"middle\" x=\"175.857\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node19\" class=\"node\"><title>18</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;18 -->\n",
       "<g id=\"edge18\" class=\"edge\"><title>17&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-429.595C180,-418.257 180,-403.227 180,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-390.095 180,-380.095 176.5,-390.095 183.5,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node22\" class=\"node\"><title>21</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-357.8\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;21 -->\n",
       "<g id=\"edge21\" class=\"edge\"><title>17&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M189.406,-432.368C197.614,-419.601 209.664,-400.856 219.169,-386.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"222.238,-387.768 224.702,-377.464 216.35,-383.983 222.238,-387.768\"/>\n",
       "<text text-anchor=\"middle\" x=\"216.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node20\" class=\"node\"><title>19</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 18&#45;&gt;19 -->\n",
       "<g id=\"edge19\" class=\"edge\"><title>18&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-343.595C180,-332.257 180,-317.227 180,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-304.095 180,-294.095 176.5,-304.095 183.5,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"184.857\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node21\" class=\"node\"><title>20</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"180\" y=\"-185.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge20\" class=\"edge\"><title>19&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-257.595C180,-246.257 180,-231.227 180,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-218.095 180,-208.095 176.5,-218.095 183.5,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1a108e6a58>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "banana_trie = suffix_trie('banana')\n",
    "draw_trie(banana_trie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5:**\n",
    "\n",
    "Write a function which returns True if a query string is in the genome represented by a suffix trie, and False if it is not. Remember we don't need to get to a leaf node, as it's ok if our query string is the prefix of one of the suffixes in a trie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def query_trie_for_existence(trie, keystring):\n",
    "    '''\n",
    "    Given a dict representing a suffix trie, and a key string,\n",
    "    return True if the key string is a prefix of any suffix in the trie,\n",
    "    and False otherwise.\n",
    "    '''\n",
    "    node = trie\n",
    "    for char in keystring:\n",
    "        if char not in node:\n",
    "            return False\n",
    "        node = node[char]\n",
    "    # We've followed the whole keystring\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie_for_existence(banana_trie, 'ana')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie_for_existence(banana_trie, 'anab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text2_trie = suffix_trie(text2)\n",
    "query_trie_for_existence(text2_trie, 'GATCGC')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie_for_existence(text2_trie, 'GAGCGC')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 6 (challenge):**\n",
    "\n",
    "Write a function which queries a suffix trie and returns either `None` (if the string is not in the trie at all) or a list of genomic coordinates (if it is).\n",
    "\n",
    "To find all coordinates in the subtree of a given node, we need to carry out a depth-first search. To make this challenge a bit easier, you can import this function from trie_utilities with `from trie_utilities import get_leaf_values()`, which implements depth-first search, or you can write it yourself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "from trie_utilities import get_leaf_values\n",
    "\n",
    "def query_trie(trie, keystring):\n",
    "    '''\n",
    "    Query given trie for keystring.\n",
    "    If it is not found, return None.\n",
    "    If it is found, return the list of genomic coordinates indexed by it.\n",
    "    '''\n",
    "    node = trie\n",
    "    for char in keystring:\n",
    "        if char not in node:\n",
    "            print(\"String not found\")\n",
    "            return None\n",
    "        node = node[char]\n",
    "    # We've followed the whole keystring, get leaf values\n",
    "    print(\"String found\")\n",
    "    return get_leaf_values(node) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "banana_trie = suffix_trie('banana')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 1]"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie(banana_trie, 'an')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {},
   "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: Suffix trie Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"646pt\"\n",
       " viewBox=\"0.00 0.00 260.00 646.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 642)\">\n",
       "<title>Suffix trie</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-642 256,-642 256,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"130\" cy=\"-620\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"37\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M117.069,-607.32C101.747,-593.481 76.0143,-570.239 57.8629,-553.844\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"59.8883,-550.957 50.1212,-546.851 55.1963,-556.152 59.8883,-550.957\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> b</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"104\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>0&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M124.863,-602.404C121.231,-590.669 116.287,-574.696 112.123,-561.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"115.427,-560.079 109.126,-551.561 108.739,-562.149 115.427,-560.079\"/>\n",
       "<text text-anchor=\"middle\" x=\"123.857\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node17\" class=\"node\"><title>16</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"158\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;16 -->\n",
       "<g id=\"edge16\" class=\"edge\"><title>0&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M135.399,-602.804C139.324,-591.027 144.723,-574.83 149.26,-561.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"152.68,-562.027 152.522,-551.433 146.04,-559.813 152.68,-562.027\"/>\n",
       "<text text-anchor=\"middle\" x=\"151.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node23\" class=\"node\"><title>22</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"212\" cy=\"-534\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212\" y=\"-529.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;22 -->\n",
       "<g id=\"edge22\" class=\"edge\"><title>0&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M142.099,-606.606C155.423,-592.957 177.03,-570.823 192.699,-554.772\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"195.37,-557.046 199.851,-547.445 190.361,-552.156 195.37,-557.046\"/>\n",
       "<text text-anchor=\"middle\" x=\"181.25\" y=\"-572.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.1551,-516.001C30.5369,-504.426 27.0177,-488.868 24.0296,-475.657\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.3944,-474.668 21.7744,-465.687 20.5669,-476.212 27.3944,-474.668\"/>\n",
       "<text text-anchor=\"middle\" x=\"33.8569\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-429.595C18,-418.257 18,-403.227 18,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-390.095 18,-380.095 14.5001,-390.095 21.5001,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-343.595C18,-332.257 18,-317.227 18,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-304.095 18,-294.095 14.5001,-304.095 21.5001,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.8569\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-257.595C18,-246.257 18,-231.227 18,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-218.095 18,-208.095 14.5001,-218.095 21.5001,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-171.595C18,-160.257 18,-145.227 18,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-132.095 18,-122.095 14.5001,-132.095 21.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.8569\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-85.5951C18,-74.2572 18,-59.2271 18,-46.3153\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-46.0951 18,-36.0952 14.5001,-46.0952 21.5001,-46.0951\"/>\n",
       "<text text-anchor=\"middle\" x=\"23.25\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\"><title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M97.8301,-516.804C93.2703,-504.835 86.9716,-488.3 81.7356,-474.556\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"84.9817,-473.245 78.151,-465.146 78.4403,-475.737 84.9817,-473.245\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.25\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\"><title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-443.8\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\"><title>8&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.346,-516.404C111.42,-504.669 115.603,-488.696 119.127,-475.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"122.515,-476.122 121.663,-465.561 115.743,-474.348 122.515,-476.122\"/>\n",
       "<text text-anchor=\"middle\" x=\"122.25\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\"><title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-429.595C72,-418.257 72,-403.227 72,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-390.095 72,-380.095 68.5001,-390.095 75.5001,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"76.8569\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\"><title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\"><title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-343.595C72,-332.257 72,-317.227 72,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-304.095 72,-294.095 68.5001,-304.095 75.5001,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\"><title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-271.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\"><title>10&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.4061,-346.368C89.6139,-333.601 101.664,-314.856 111.169,-300.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"114.238,-301.768 116.702,-291.464 108.35,-297.983 114.238,-301.768\"/>\n",
       "<text text-anchor=\"middle\" x=\"108.25\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\"><title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\"><title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-257.595C72,-246.257 72,-231.227 72,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-218.095 72,-208.095 68.5001,-218.095 75.5001,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"76.8569\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\"><title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"72\" cy=\"-104\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\"><title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72,-171.595C72,-160.257 72,-145.227 72,-132.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.5001,-132.095 72,-122.095 68.5001,-132.095 75.5001,-132.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.25\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node18\" class=\"node\"><title>17</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-448\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\"><title>16&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.346,-516.404C165.42,-504.669 169.603,-488.696 173.127,-475.244\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"176.515,-476.122 175.663,-465.561 169.743,-474.348 176.515,-476.122\"/>\n",
       "<text text-anchor=\"middle\" x=\"175.857\" y=\"-486.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node19\" class=\"node\"><title>18</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;18 -->\n",
       "<g id=\"edge18\" class=\"edge\"><title>17&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-429.595C180,-418.257 180,-403.227 180,-390.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-390.095 180,-380.095 176.5,-390.095 183.5,-390.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> n</text>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node22\" class=\"node\"><title>21</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-362\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-357.8\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;21 -->\n",
       "<g id=\"edge21\" class=\"edge\"><title>17&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M189.406,-432.368C197.614,-419.601 209.664,-400.856 219.169,-386.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"222.238,-387.768 224.702,-377.464 216.35,-383.983 222.238,-387.768\"/>\n",
       "<text text-anchor=\"middle\" x=\"216.25\" y=\"-400.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node20\" class=\"node\"><title>19</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-276\" rx=\"18\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 18&#45;&gt;19 -->\n",
       "<g id=\"edge19\" class=\"edge\"><title>18&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-343.595C180,-332.257 180,-317.227 180,-304.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-304.095 180,-294.095 176.5,-304.095 183.5,-304.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"184.857\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\"> a</text>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node21\" class=\"node\"><title>20</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-190\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"180\" y=\"-185.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge20\" class=\"edge\"><title>19&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180,-257.595C180,-246.257 180,-231.227 180,-218.315\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.5,-218.095 180,-208.095 176.5,-218.095 183.5,-218.095\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.25\" y=\"-228.8\" font-family=\"Times,serif\" font-size=\"14.00\"> $</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1176e2160>"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_trie(banana_trie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "phiX_trie = suffix_trie(phiX)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "String found\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[6, 64, 346, 148, 42, 439, 709, 638, 619, 248, 282, 566, 641, 940]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie(phiX_trie, 'TAT')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "String found\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[42]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query_trie(phiX_trie, 'TATTT')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "String not found\n"
     ]
    }
   ],
   "source": [
    "query_trie(phiX_trie, 'TATGGG')"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}