CG_NaiveApprox.json

{
 "metadata": {
  "name": "CG_NaiveApprox"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Like the naive algorithm but we break out of the inner loop as soon as our\n",
      "# mismatch budget exceeds the maximum allowed Hamming distance.\n",
      "def naiveApproximate(p, t, maxHammingDistance=1):\n",
      "    occurrences = []\n",
      "    for i in xrange(0, len(t) - len(p) + 1): # for all alignments\n",
      "        nmm = 0\n",
      "        for j in xrange(0, len(p)):          # for all characters\n",
      "            if t[i+j] != p[j]:               # does it match?\n",
      "                nmm += 1                     # mismatch\n",
      "                if nmm > maxHammingDistance:\n",
      "                    break                    # exceeded maximum distance\n",
      "        if nmm <= maxHammingDistance:\n",
      "            # approximate match; return pair where first element is the\n",
      "            # offset of the match and second is the Hamming distance\n",
      "            occurrences.append((i, nmm))\n",
      "    return occurrences"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "naiveApproximate('needle', 'needle noodle nargle', maxHammingDistance=2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "[(0, 0), (7, 2)]"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    }
   ],
   "metadata": {}
  }
 ]
}