trie_construction.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "szfg\n"
     ]
    }
   ],
   "source": [
    "# CONSTRUCTING A TRIE FROM A GIVEN SET OF PATTERNS (ALONG WITH THE PSEUDO CODE)\n",
    "# The following code is the solution for a code challenge from Coursera's course:\n",
    "# \"Finding Mutations in DNA and Proteins (Bioinformatics VI)Week 1\" \n",
    "# For details regarding the Trie Construction Problem please visit https://www.coursera.org/learn/dna-mutations \n",
    "\n",
    "#Code Challenge: Solve the Trie Construction Problem.\n",
    "\n",
    "#Input: A collection of strings Patterns.\n",
    "#Output: The adjacency list corresponding to Trie(Patterns), in the following format. If Trie(Patterns) has n nodes, \n",
    "#first label the root with 0 and then label the remaining nodes with the integers 1 through n - 1 in any order you like. \n",
    "#Each edge of the adjacency list of Trie(Patterns) will be encoded by a triple: the first two members of the triple must be \n",
    "#the integers labeling the initial and terminal nodes of the edge, respectively; the third member of the triple must be the symbol labeling the edge.\n",
    "\n",
    "######PSEUDO CODE START######\n",
    "\"\"\" \n",
    "TrieConstruction(Patterns)\n",
    "    Trie ← a graph consisting of a single node root\n",
    "    for each string Pattern in Patterns\n",
    "        currentNode ← root\n",
    "        for i ← 0 to |Pattern| - 1\n",
    "            currentSymbol ← Pattern[i]\n",
    "            if there is an outgoing edge from currentNode with label currentSymbol\n",
    "                currentNode ← ending node of this edge\n",
    "            else\n",
    "                add a new node newNode to Trie\n",
    "                add a new edge from currentNode to newNode with label currentSymbol\n",
    "                currentNode ← newNode\n",
    "    return Trie\n",
    "\"\"\"\n",
    "######PSEUDO CODE END######\n",
    "\n",
    "def trie_construction(patterns):\n",
    "    # initialising the trie with a root node as 0\n",
    "    # we are representing the trie as dictionary of dictionaries\n",
    "    trie = {0:{}}\n",
    "    # looping over each pattern in the input list of patterns\n",
    "    for each_pattern in patterns:\n",
    "        # for every pattern we start with the root node\n",
    "        current_node = 0\n",
    "        # looping over every character of the pattern\n",
    "        for i in range(len(each_pattern)):\n",
    "            current_symbol = each_pattern[i]\n",
    "            # checking if our current node has an edge labelled with our current symbol\n",
    "            # if true, we move to the connecting node for this edge\n",
    "            if current_symbol in trie[current_node]:\n",
    "                current_node = trie[current_node][current_symbol] \n",
    "            \n",
    "            # if our current node does not have an edge labelled with our current symbol, then\n",
    "            # create a edge labelled with our current symbol, connecting our cuurent node to a new node\n",
    "            # and then move to this new node\n",
    "            else:\n",
    "                node = len(trie)\n",
    "                trie[current_node][current_symbol] = node\n",
    "                trie[node] = {} \n",
    "                current_node = node\n",
    "                \n",
    "    return trie\n",
    "\n",
    "\n",
    "input_file_path = r\"D:\\Python_for_Bioinformatics\\PFB_clients\\Custom_Script__Development\\Ekta_dadlani\\cc_1\\dataset_294_4.txt\"\n",
    "out_file_path = r\"D:\\Python_for_Bioinformatics\\PFB_clients\\Custom_Script__Development\\Ekta_dadlani\\cc_1\\adjacency_list.txt\"\n",
    "\n",
    "# reading our input file and creating a list for the patterns given in the file\n",
    "fr = open(input_file_path,\"r\")\n",
    "patterns = fr.read().split(\"\\n\")\n",
    "fr.close()\n",
    "\n",
    "# calling the trie_construction(patterns) function\n",
    "trie = trie_construction(patterns)\n",
    "\n",
    "# writing the adjacency list to a file\n",
    "fw = open(out_file_path,\"w\")\n",
    "adjacency_list = []\n",
    "for node in trie:\n",
    "    for edge_label in trie[node]: \n",
    "        line = str(node) + \"->\" + str(trie[node][edge_label]) + \":\" + edge_label\n",
    "        adjacency_list.append(line)\n",
    "\n",
    "fw.write(\"\\n\".join(adjacency_list))\n",
    "fw.close()\n",
    "\n"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}