src/explore_needle_wunsch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Global Sequence Alignment with Needleman-Wunsch\n",
    "\n",
    "This notebook shows the how a list of partial transcripts are aligned with a full transcript using the _Needleman-Wunsch_ algorithm.\n",
    "\n",
    "## How it works\n",
    "\n",
    "The _Needleman Wunsch_ (NW) algorithm alignms string $B$ with string $A$ by deleting characters or inserting gaps in one of the strings. It is very similar to the _Smith Waterman_ (SW) algorithm. However, whereas the latter performs a local aligment, NW performs a global alignment, i.e. the optimal alignment for all partial transcripts is found. Like the SW algorithm, NW calculates an alignment matrix first, containing the costs for insertion/deletion of characters and then backtracks that matrix.\n",
    "\n",
    "## The extended algorithm\n",
    "\n",
    "To align the partial transcript with the full transcript, they are concatenated and separated by space. The concatenated transcripts are used as string $B$ (the string to be aligned) and the full transcript as string $A$ (the reference string). The implementation for NW used in this project was inspired by [this implementation by Aleksander Levchuck](https://github.com/alevchuk/pairwise-alignment-in-python/blob/master/alignment.py). However some optimizations and additions were made.\n",
    "\n",
    "Because we do not want to lose the information where the start and endings of a partial transcript are aligned, the _boundaries_, i.e. the indices of the positions in $B$ where a partial transcript starts and ends must be supplied to the function. The following example sentence serves as an example (the partial alignments are single words)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from util.gsa_util import needle_wunsch\n",
    "\n",
    "a = 'ich bin ein berliner'\n",
    "partial_transcripts = ['ach', 'bene', 'ain', 'berlinör']\n",
    "b = ' '.join(partial_transcripts)\n",
    "boundaries = []\n",
    "for p in partial_transcripts:\n",
    "    boundaries += [(b.index(p), b.index(p) + len(p))]\n",
    "    \n",
    "print('A:', a)\n",
    "print('B:', b)\n",
    "print('boundaries:', boundaries)\n",
    "print()\n",
    "\n",
    "alignments, source_str, target_str = needle_wunsch(a, b, boundaries)\n",
    "print('A (aligned):', source_str)\n",
    "print('B (aligned):', target_str)\n",
    "print()\n",
    "for t, al in zip(partial_transcripts, alignments):\n",
    "    start = al['start']\n",
    "    end = al['end']\n",
    "    text = al['text']\n",
    "    \n",
    "    print(f'partial transcript: {t}, aligned text: {text} (A[{start}:{end}])')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating the boundaries\n",
    "\n",
    "Calculating the boundaries is cumbersome. That's why it is integrated in the LSA-Stage of the pipeline."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pipeline import gsa\n",
    "\n",
    "transcript = 'ich bin ein berliner'\n",
    "partial_transcripts = ['ach', 'bene', 'ain', 'berlinör']\n",
    "\n",
    "alignments = gsa(transcript, partial_transcripts, align_endings=True)\n",
    "    \n",
    "for t, al in zip(partial_transcripts, alignments):\n",
    "    start = al['start']\n",
    "    end = al['end']\n",
    "    text = al['text']\n",
    "    \n",
    "    print(f'partial transcript: {t}, aligned text: {text} (A[{start}:{end}])')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GSA also works for longer texts, although it can become quite slow then."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from util.string_util import normalize\n",
    "from pipeline import gsa\n",
    "\n",
    "transcript = \"\"\"\n",
    "My fellow Americans,\n",
    "\n",
    "This week, prosecutors, law enforcement officers, homeland security officials, and lawmakers joined me at the White House to address a very vicious threat to our communities—the savage gang, MS-13.\n",
    "\n",
    "Glaring loopholes in our laws have allowed criminals and gang members to break into our country. For example, under current law, unaccompanied alien minors at the border are released into American communities no matter where, no matter how, it is so easy for them because the laws are bad and they have to be changed. This loophole is easily exploited by MS-13, which now operates in at least 40 states.\n",
    "\n",
    "In addition to MS-13, many other gangs are breaking into our country routinely because our laws are so weak, so sad, so pathetic.\n",
    "\n",
    "At this week’s roundtable, we learned the story of one family right here in Washington, D.C. that hosted a person in their home, who then began to recruit their young son to MS-13. When the boy’s mother tried to stop it, the gang member shot her in the head, blinding her for life. She’s lucky she lived, but she’s paying a very big price.\n",
    "\n",
    "During my State of the Union, I called on Congress to immediately close dangerous loopholes in federal law that have endangered our communities and imposed enormous burdens on U.S. taxpayers.\n",
    "\n",
    "My Administration has identified three major priorities for creating a safe, modern and lawful immigration system: fully securing the border, ending chain migration, and canceling the visa lottery. Chain migration is a disaster and very unfair to our country. The visa lottery is something that should have never been allowed in the first place. People enter a lottery to come into our country. What kind of a system is that? It is time for Congress to act and to protect Americans. Every member of Congress should choose the side of law enforcement, and the side of the American People. That’s the way it has to be.\n",
    "\"\"\"\n",
    "print(f'transcript (A) length: {len(transcript)}')\n",
    "\n",
    "partial_transcripts = \"\"\"\n",
    "my fellow Americans\n",
    "this week prosecutors law enforcement offices Homeland Security officials\n",
    "lawmakers join me at the White House to address\n",
    "a very vicious threat to our communities\n",
    "The Savage gang MS-13\n",
    "glaring loopholes in our laws have allowed criminals and gang members to break into our country\n",
    "for example\n",
    "under current law unaccompanied alien minors at the border\n",
    "are released into American communities no matter where\n",
    "no matter how\n",
    "so easy for them because the laws are bad and they have to be changed\n",
    "this loophole is easily exploited by MS-13\n",
    "which now operates in at least 40 States\n",
    "in addition to MS-13\n",
    "many other gangs are breaking into our country routinely\n",
    "because I lost the show week\n",
    "so sad\n",
    "at this week's Roundtable we learned the story of one family right here in Washington DC\n",
    "that hosted a person in their home\n",
    "who then began to recruit their young son\n",
    "do MS-13\n",
    "when the boy's mother tried to stop it the gang member shot her in the head\n",
    "blinding her for life\n",
    "she's lucky she lived but she's paying a very big price\n",
    "during my state of the union I called on Congress to immediately close dangerous loopholes in federal law\n",
    "that have endangered our communities\n",
    "an imposed enormous burdens on us taxpayers\n",
    "my Administration has identified three major priorities\n",
    "creating a safe\n",
    "modern and lawful immigration system fully security the Border\n",
    "ending chain migration\n",
    "I'm cancelling the Visa Lottery\n",
    "chain migration is a disaster and very unfair to our country\n",
    "the Visa Lottery is something that should have never been allowed in the first place\n",
    "people enter a lottery to come into our country\n",
    "what kind of a system is that\n",
    "is time for Congress to act and to protect Americans\n",
    "every member of Congress should choose the side of law enforcement\n",
    "by the side of the American people\n",
    "that's the way it has to be\n",
    "\"\"\"\n",
    "partial_transcripts = [line.strip() for line in partial_transcripts.splitlines() if line.strip()]\n",
    "print(f'{len(partial_transcripts)} partial transcripts')\n",
    "b = ' '.join(partial_transcripts)\n",
    "print(f'concatenated partial transcripts (B) length: {len(b)}')\n",
    "\n",
    "alignments = gsa(transcript, partial_transcripts, align_endings=True)\n",
    "\n",
    "for p, al in zip(partial_transcripts, alignments):\n",
    "    print('partial transcript:', p)\n",
    "    print('aligned text      :', al['text'])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aligning the partial transcripts\n",
    "\n",
    "The _Precision_ of alignments is calculated as the _Levenshtein Similarity_ between a partial transcript and its aligned text. _Recall_ is measured as how much of the full transcript is covered by the aligned texts. Because alignments should neither start nor end within words, the start and/or end index of an alignment is moved so it falls on a beginning or end of a word (whichever is closer). If the start/end index of an alignment happens to fall within a sequence of whitespace characters (space, newline, ...) it is moved to the right (start index) resp. to the left (end index) until a non-whitespace character is encountered. This prevents aligned texts containing spaces or line breaks at the start and beginning.\n",
    "\n",
    "### Handling boundaries\n",
    "\n",
    "With given boundaries the start of each partial transcript will be aligned in the full transcript. Aligning the end of each transcript (method 1) is optional. Doing so will lead to more accurate alignemnts (higher Precision) because each aligned text will have been aligned exactly with the characters of the corresponding partial transcript. On the other hand, aligning both start and end of each partial transcript will possibly lead to unaligned characters in the transcript (lower Recall). Consider the following example:\n",
    "\n",
    "```\n",
    "Full transcript    : I see, I see, said the blind man to his deaf daughter.\n",
    "   alignments      : xxxxx---------xxxxxxxxxxxxxx-----xxxxxxxxxxxxxxxxxxxx-\n",
    "Partial transcripts: i see         sed da blnd        dois death dooter\n",
    "   Precision          1.0              0.57                 0.55\n",
    "\n",
    "xxx = aligned parts\n",
    "--- = unaligned parts\n",
    "\n",
    "av. Precision: 0.71\n",
    "av. Recall: 0.65\n",
    "```\n",
    "\n",
    "When not aligning the ends of the alignments (method 2) will simply move the end of each alignment to where the next alignment starts. This will prevent having unaligned text in the transcript (high Recall), although the alignments may contain text that is not spoken or would actually belong to the next alignment. Note that unaligned text is still possible at the very start or end of the full transcript. Consider the same example as above, but this time not aligning the endings:\n",
    "\n",
    "```\n",
    "Full transcript    : I see, I see, said the blind man to his deaf daughter.\n",
    "   alignments      : xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\n",
    "Partial transcripts: i see         sed  da  blnd      dois death dooter\n",
    "   Precision             0.36          0.37                 0.52\n",
    "\n",
    "xxx = aligned parts\n",
    "--- = unaligned parts\n",
    "\n",
    "av. Precision: 0.42\n",
    "av. Recall: 1.00\n",
    "```\n",
    "\n",
    "Above procedures show the trade-off which usually happens when dealing with Precision and Recall: You can't have high values for both. Because a lower Recall is not necessarily bad (there may be annotations, footnotes, etc., which are not read), the default alignment method is to align both start and end of each partial transcript."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}