Skip to content

Instantly share code, notes, and snippets.

@BenLangmead
Created November 13, 2013 16:41
Show Gist options
  • Save BenLangmead/7452174 to your computer and use it in GitHub Desktop.
Save BenLangmead/7452174 to your computer and use it in GitHub Desktop.
{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "code",
"collapsed": false,
"input": [
"def traceLcs(D, x, y):\n",
" ''' Backtrace for LCS; returns LCS as string. '''\n",
" i, j = len(x), len(y) # start in lower-right\n",
" st = []\n",
" while i > 0 and j > 0:\n",
" # get the three contributions\n",
" diag, vert, horz = 0, 0, 0\n",
" if i > 0 and j > 0:\n",
" delt = -1 if x[i-1] == y[j-1] else 1\n",
" diag = D[i-1, j-1] + delt\n",
" if i > 0: vert = D[i-1, j]\n",
" if j > 0: horz = D[i, j-1]\n",
" if diag <= vert and diag <= horz:\n",
" # diagonal is best, thus, this char is part of LCS\n",
" st.append(x[i-1])\n",
" i -= 1; j -= 1 # move up and left\n",
" elif vert <= horz: i -= 1 # vertical is best; move up\n",
" else: j -= 1 # horizontal is best; move left\n",
" # reverse it, then return string-ized LCS\n",
" return (''.join(st))[::-1]\n",
"\n",
"import numpy\n",
"def lcsDp(x, y):\n",
" ''' Return LCS of x and y. Uses bottom-up dynamic programming\n",
" approach. '''\n",
" D = 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",
" delt = -1 if x[i-1] == y[j-1] else 1\n",
" D[i, j] = min(D[i-1, j-1] + delt, D[i-1, j], D[i, j-1])\n",
" return traceLcs(D, x, y), D"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"lcs, D = lcsDp('ATCTGAT', 'TGCATA') # example from Jones & Pevzner 6.5\n",
"lcs"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"'TCTA'"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"D"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 3,
"text": [
"array([[ 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, -1, -1, -1],\n",
" [ 0, -1, -1, -1, -1, -2, -2],\n",
" [ 0, -1, -1, -2, -2, -2, -2],\n",
" [ 0, -1, -1, -2, -2, -3, -3],\n",
" [ 0, -1, -2, -2, -2, -3, -3],\n",
" [ 0, -1, -2, -2, -3, -3, -4],\n",
" [ 0, -1, -2, -2, -3, -4, -4]])"
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment