CG_DP_Local.json

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy\n",
      "\n",
      "def exampleCost(xc, yc):\n",
      "    ''' Cost function: 2 to match, -6 to gap, -4 to mismatch '''\n",
      "    if xc == yc: return 2 # match\n",
      "    if xc == '-' or yc == '-': return -6 # gap\n",
      "    return -4\n",
      "\n",
      "def smithWaterman(x, y, s):\n",
      "    ''' Calculate local alignment values of sequences x and y using\n",
      "        dynamic programming.  Return maximal local alignment value. '''\n",
      "    V = numpy.zeros((len(x)+1, len(y)+1), dtype=int)\n",
      "    for i in xrange(1, len(x)+1):\n",
      "        for j in xrange(1, len(y)+1):\n",
      "            V[i, j] = max(V[i-1, j-1] + s(x[i-1], y[j-1]), # diagonal\n",
      "                          V[i-1, j  ] + s(x[i-1], '-'),    # vertical\n",
      "                          V[i  , j-1] + s('-',    y[j-1]), # horizontal\n",
      "                          0)                               # empty\n",
      "    argmax = numpy.where(V == V.max())\n",
      "    return V, int(V[argmax])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "V, best = smithWaterman('GGTATGCTGGCGCTA', 'TATATGCGGCGTTT', exampleCost)\n",
      "print (V)\n",
      "print \"Best: %d\" % best"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]\n",
        " [ 0  0  0  0  0  0  2  0  2  2  0  2  0  0  0]\n",
        " [ 0  0  0  0  0  0  2  0  2  4  0  2  0  0  0]\n",
        " [ 0  2  0  2  0  2  0  0  0  0  0  0  4  2  2]\n",
        " [ 0  0  4  0  4  0  0  0  0  0  0  0  0  0  0]\n",
        " [ 0  2  0  6  0  6  0  0  0  0  0  0  2  2  2]\n",
        " [ 0  0  0  0  2  0  8  2  2  2  0  2  0  0  0]\n",
        " [ 0  0  0  0  0  0  2 10  4  0  4  0  0  0  0]\n",
        " [ 0  2  0  2  0  2  0  4  6  0  0  0  2  2  2]\n",
        " [ 0  0  0  0  0  0  4  0  6  8  2  2  0  0  0]\n",
        " [ 0  0  0  0  0  0  2  0  2  8  4  4  0  0  0]\n",
        " [ 0  0  0  0  0  0  0  4  0  2 10  4  0  0  0]\n",
        " [ 0  0  0  0  0  0  2  0  6  2  4 12  6  0  0]\n",
        " [ 0  0  0  0  0  0  0  4  0  2  4  6  8  2  0]\n",
        " [ 0  2  0  2  0  2  0  0  0  0  0  0  8 10  4]\n",
        " [ 0  0  4  0  4  0  0  0  0  0  0  0  2  4  6]]\n",
        "Best: 12\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    }
   ],
   "metadata": {}
  }
 ]
}