Week50.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# New project: Comparing DNA\n",
    "\n",
    "This week is all about explaining the questions and understanding the solution (no code).\n",
    "\n",
    "DNA comparison question:\n",
    "* Input: two DNA sequences\n",
    "* Output: The number of operations it takes to transform one sequence into the other\n",
    "* Operations: insert, delete, replace\n",
    "* For example \"ACTG\" -> \"AGCGT\" takes 3 operations:\n",
    "    * insert a \"G\" between \"A\" and \"C\" (\"ACTG\" -> \"AGCTG\")\n",
    "    * remove the \"T\" (\"AGCTG\" -> \"AGCG\")\n",
    "    * insert a \"T\" at the end (\"AGCG\" -> \"AGCGT\")\n",
    "* NOTE: THIS IS THE EDIT DISTANCE PROBLEM\n",
    "\n",
    "Solution:\n",
    "* Brute force: try all possible transformations and pick the one with the least operations\n",
    "* The solution is based on dynamic programming\n",
    "* Create a table where each cell denotes the cost of transforming one substring into another\n",
    "\n",
    "    |   | A | G | C | G | T |\n",
    "    |---|---|---|---|---|---|\n",
    "    | A | 0 | 1 | 2 | 3 | 4 |\n",
    "    | C | 1 | 1 | 1 | 2 | 3 |\n",
    "    | T | 2 | 2 | 2 | 2 | 2 |\n",
    "    | G | 3 | 2 | 3 | 2 | 3 |\n",
    "* The cost of transforming one substring into another is the minimum of:\n",
    "    * Adding: The cost of transforming the substring without the last character into the other substring plus 1\n",
    "    * Removing: The cost of transforming the substring into the other substring without the last character plus 1\n",
    "    * Changing: The cost of transforming the substring without the last character into the other substring without the last character plus 1 if the last characters are different, 0 otherwise"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}