homework-3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'TTGAATGCTGAAATCAGCAGGTAATATATGATAATAGAGAAAGCTATCCCGAAGGTGCATAGGTCAACAATACTTGAGCCTAACTCAGTAGATCCTAAAA'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def readGenome(filename):\n",
    "    genome = ''\n",
    "    with open(filename, 'r') as f:\n",
    "        for line in f:\n",
    "            # ignore header line with genome information\n",
    "            if not line[0] == '>':\n",
    "                genome += line.rstrip()\n",
    "    return genome\n",
    "chr1 = readGenome('chr1.GRCh38.excerpt.fasta')\n",
    "chr1[:100]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def approximate_match(p, t):\n",
    "    # Create distance matrix\n",
    "    D = []\n",
    "    for i in range(len(p)+1):\n",
    "        D.append([0]*(len(t)+1))\n",
    "       \n",
    "    # Initialize first row and column of matrix\n",
    "    for i in range(len(p)+1):\n",
    "        D[i][0] = i\n",
    "    for i in range(len(t)+1):\n",
    "        D[0][i] = 0\n",
    "       \n",
    "    # Fill in the rest of the matrix\n",
    "    for i in range(1, len(p)+1):\n",
    "        for j in range(1, len(t)+1):\n",
    "            distHor = D[i][j-1] + 1\n",
    "            distVer = D[i-1][j] + 1\n",
    "            if p[i-1] == t[j-1]:\n",
    "                distDiag = D[i-1][j-1]\n",
    "            else:\n",
    "                distDiag = D[i-1][j-1] + 1\n",
    "            D[i][j] = min(distHor, distVer, distDiag)\n",
    "       \n",
    "    # Edit distance is the value in the bottom right corner of the matrix\n",
    "    return min(D[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def overlap(a, b, min_length=3):\n",
    "    \"\"\" Return length of longest suffix of 'a' matching\n",
    "        a prefix of 'b' that is at least 'min_length'\n",
    "        characters long.  If no such overlap exists,\n",
    "        return 0. \"\"\"\n",
    "    start = 0  # start all the way at the left\n",
    "    while True:\n",
    "        start = a.find(b[:min_length], start)  # look for b's suffx in a\n",
    "        if start == -1:  # no more occurrences to right\n",
    "            return 0\n",
    "        # found occurrence; check for full suffix/prefix match\n",
    "        if b.startswith(a[start:]):\n",
    "            return len(a)-start\n",
    "        start += 1  # move just past previous match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "def overlap_graph(reads, k):\n",
    "    # Make index\n",
    "    index = defaultdict(set)\n",
    "    for read in reads:\n",
    "        for i in range(len(read) - k + 1):\n",
    "            index[read[i:i+k]].add(read)\n",
    "\n",
    "    # Make graph\n",
    "    graph = defaultdict(set)\n",
    "    for r in reads:\n",
    "        for o in index[r[-k:]]:\n",
    "            if r != o:\n",
    "                if overlap(r, o, k):\n",
    "                    graph[r].add(o)\n",
    "\n",
    "    edges = 0\n",
    "    for read in graph:\n",
    "        edges += len(graph[read])\n",
    "    return(edges, len(graph))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "p = 'GCTGATCGATCGTACG'\n",
    "print(approximate_match(p, chr1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "p = 'GATTTACCAGATTGAG'\n",
    "print(approximate_match(p, chr1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "def readFastq(filename):\n",
    "    sequences = []\n",
    "    qualities = []\n",
    "    with open(filename) as fh:\n",
    "        while True:\n",
    "            fh.readline()  # skip name line\n",
    "            seq = fh.readline().rstrip()  # read base sequence\n",
    "            fh.readline()  # skip placeholder line\n",
    "            qual = fh.readline().rstrip()  # base quality line\n",
    "            if len(seq) == 0:\n",
    "                break\n",
    "            sequences.append(seq)\n",
    "            qualities.append(qual)\n",
    "    return sequences, qualities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "904746\n",
      "7161\n"
     ]
    }
   ],
   "source": [
    "seqs, quals = readFastq('ERR266411_1.for_asm.fastq')\n",
    "edges, suffixes = overlap_graph(seqs, 30)\n",
    "print(edges)\n",
    "print(suffixes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}