{ "cells": [ { "cell_type": "markdown", "id": "4dc97634", "metadata": { "id": "4dc97634" }, "source": [ "# Smith-Waterman algorithm\n", "\n", "This notebook uses the Smith-Waterman algorithm to find *local* regions of alignment between two pieces of text." ] }, { "cell_type": "code", "execution_count": null, "id": "bed56919", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "bed56919", "outputId": "e265888e-dc4d-4e43-a880-3b08df3fe7b5" }, "outputs": [], "source": [ "import re\n", "\n", "import nltk\n", "from nltk import word_tokenize\n", "import numpy as np\n", "\n", "nltk.download(\"punkt\")\n", "nltk.download(\"punkt_tab\")" ] }, { "cell_type": "code", "execution_count": null, "id": "cfe9667a", "metadata": { "id": "cfe9667a" }, "outputs": [], "source": [ "def base_similarity(token1, token2):\n", " return 3 if token1 == token2 else -3" ] }, { "cell_type": "code", "execution_count": null, "id": "64e59d0d", "metadata": { "id": "64e59d0d" }, "outputs": [], "source": [ "def smith_waterman(one, two, similarity_function, visualize=False):\n", " indel = -2\n", "\n", " # columns\n", " m = len(one)\n", " # rows\n", " n = len(two)\n", " scores = np.zeros((n + 1, m + 1))\n", " backpointers = np.ones((n + 1, m + 1), dtype=int) * -1\n", "\n", " maxtotal = 0\n", " maxrow = -1\n", " maxcol = -1\n", "\n", " # Calculate similarity scores\n", " # rows\n", " for i in range(1, n + 1):\n", " # columns\n", " for j in range(1, m + 1):\n", " left = scores[i, j - 1] + indel\n", " top = scores[i - 1, j] + indel\n", " diag = scores[i - 1, j - 1] + similarity_function(one[j - 1], two[i - 1])\n", "\n", " maxx = top\n", " backpointers[i, j] = 0\n", " if left > maxx:\n", " maxx = left\n", " backpointers[i, j] = 1\n", " if diag > maxx:\n", " maxx = diag\n", " backpointers[i, j] = 2\n", "\n", " scores[i, j] = maxx\n", "\n", " if scores[i, j] < 0:\n", " scores[i, j] = 0\n", "\n", " if scores[i, j] > maxtotal:\n", " maxtotal = scores[i, j]\n", " maxrow = i\n", " maxcol = j\n", "\n", " argscores = np.dstack(np.unravel_index(np.argsort(-scores.ravel()), (n + 1, m + 1)))[0]\n", "\n", " all_alignments = []\n", " seen_best = {}\n", "\n", " # only show sequences that have a score of 10 or higher\n", " # (with a similarity_function score of 3, this effectively means >3 words must be aligned)\n", "\n", " min_score = 10\n", "\n", " # this loop finds all alignments between the source and target, but only allows each word\n", " # in the source and target sequence to belong to *one* alignment.\n", "\n", " for top_n in range(len(argscores)):\n", "\n", " overlap_flag = False\n", " source_alignments = []\n", " row, col = argscores[top_n]\n", " score = scores[row, col]\n", " if score < min_score:\n", " break\n", "\n", " start = backpointers[row, col]\n", "\n", " this_seen_best = {}\n", "\n", " if (\"C\", col - 1) in seen_best or (\"R\", row - 1) in seen_best:\n", " continue\n", "\n", " while score > 0:\n", " if start == 0:\n", " row -= 1\n", " if start == 1:\n", " col -= 1\n", " if start == 2:\n", " if one[col - 1] == two[row - 1] and re.search(\"\\S\", one[col - 1]) != None:\n", " if (\"C\", col - 1) not in seen_best and (\"R\", row - 1) not in seen_best:\n", " source_alignments.append((col - 1, row - 1))\n", " else:\n", " overlap_flag = True\n", " break\n", " this_seen_best[(\"C\", col - 1)] = 1\n", " this_seen_best[(\"R\", row - 1)] = 1\n", "\n", " row -= 1\n", " col -= 1\n", " start = backpointers[row, col]\n", " score = scores[row, col]\n", "\n", " if not overlap_flag:\n", " for key in this_seen_best:\n", " seen_best[key] = 1\n", " max_left_source = m\n", " max_right_source = 0\n", " max_left_target = n\n", " max_right_target = 0\n", " for s, t in source_alignments:\n", " if s < max_left_source:\n", " max_left_source = s\n", " if s > max_right_source:\n", " max_right_source = s\n", " if t < max_left_target:\n", " max_left_target = t\n", " if t > max_right_target:\n", " max_right_target = t\n", "\n", " row,col = argscores[top_n]\n", " all_alignments.append((scores[row, col], source_alignments, max_left_source, max_right_source, max_left_target, max_right_target))\n", "\n", " return all_alignments\n" ] }, { "cell_type": "code", "execution_count": null, "id": "169518c9", "metadata": { "id": "169518c9" }, "outputs": [], "source": [ "def sw_compare(one_string, two_string, similarity_function, visualize=False):\n", " one = word_tokenize(one_string)\n", " two = word_tokenize(two_string)\n", "\n", " alignments = smith_waterman(one, two, similarity_function, visualize=visualize)\n", " for score, source_alignments, left_source, right_source, left_target, right_target in alignments:\n", " print(\"_score: %d\\n\" % score)\n", " print(\"one (%d, %d):\" % (left_source, right_source), ' '.join(one[left_source:right_source+1]))\n", " print()\n", " print(\"two (%d, %d):\" % (left_target, right_target), ' '.join(two[left_target:right_target+1]))\n", " print(\"\\n==========\\n\")" ] }, { "cell_type": "code", "execution_count": null, "id": "19f8db62", "metadata": { "id": "19f8db62" }, "outputs": [], "source": [ "weird_al_eat_it = \"\"\"Just eat it, eat it, eat it, eat it\n", "Get yourself an egg and beat it\n", "Have some more chicken, have some more pie\n", "It doesn't matter if it's broiled or fried\n", "Just eat it, eat it, just eat it, eat it\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "7cd48cc2", "metadata": { "id": "7cd48cc2" }, "outputs": [], "source": [ "jackson_beat_it = \"\"\"Just beat it, beat it, beat it, beat it\n", "No one wants to be defeated\n", "Showin' how funky and strong is your fight\n", "It doesn't matter who's wrong or right\n", "Just beat it, beat it\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "9bcc837c", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "9bcc837c", "outputId": "bb82d87c-101a-4eef-efc3-ae2bbcc62d94" }, "outputs": [], "source": [ "sw_compare(weird_al_eat_it, jackson_beat_it, base_similarity, visualize=True)" ] }, { "cell_type": "code", "execution_count": null, "id": "18bf5bea", "metadata": { "id": "18bf5bea" }, "outputs": [], "source": [ "stevie_wonder_pastime_paradise = \"\"\"Been spending most their lives\n", "Living in a pastime paradise\n", "They've been spending most their lives\n", "Living in a pastime paradise\n", "They've been wasting most their time\n", "Glorifying days long gone behind\n", "They've been wasting most their days\n", "In rememberance of ignorance oldest praise\n", "Tell me who of them will come to be\n", "How many of them are you and me\n", "Dissipation\n", "Race relations\n", "Consolation\n", "Segregation\n", "Dispensation\n", "Isolation\n", "Exploitation\n", "Mutilation\n", "Mutations\n", "Miscreation\n", "Confirmation to the evils of the world\n", "Been spending most their lives\n", "Living in a future paradise\n", "They've been spending most their lives\n", "Living in a future paradise\n", "They've been looking in their minds\n", "For the days that sorrow's gone from time\n", "They keep telling of the day\n", "When the Savior of love will come to stay\n", "Tell me who of them will come to be\n", "How many of them are you and me\n", "Proclamation\n", "Of race relations\n", "Consolations\n", "Integration\n", "Verification\n", "Of revelations\n", "Acclamation\n", "World salvation\n", "Vibrations\n", "Stimulation\n", "Confirmation to the peace of the world\n", "They've been spending most their lives\n", "Living in a pastime paradise\n", "They've been spending most their lives\n", "Living in a pastime paradise\n", "They've been spending most their lives\n", "Living in a future paradise\n", "They've been spending most their lives\n", "Living in a future paradise\n", "We've been spending too much of our lives\n", "Living in a pastime paradise\n", "Let's start living our lives\n", "Living for the future paradise\n", "Praise to our lives\n", "Living in the future paradise\n", "Shame to anyone lives\n", "Living in a pastime paradise\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "763c0ffe", "metadata": { "id": "763c0ffe" }, "outputs": [], "source": [ "coolio_gangtas_paradise = \"\"\"As I walk through the valley of the shadow of death\n", "I take a look at my life and realize there's nothing left\n", "'Cause I've been blasting and laughing so long that\n", "Even my momma thinks that my mind is gone\n", "But I ain't never crossed a man that didn't deserve it\n", "Me be treated like a punk, you know that's unheard of\n", "You better watch how you talking and where you walking\n", "Or you and your homies might be lined in chalk\n", "I really hate to trip, but I gotta loc\n", "As they croak, I see myself in the pistol smoke\n", "Fool, I'm the kinda G the little homies wanna be like\n", "On my knees in the night, saying prayers in the streetlight\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Look at the situation they got me facing\n", "I can't live a normal life, I was raised by the street\n", "So I gotta be down with the hood team\n", "Too much television watchin', got me chasing dreams\n", "I'm a educated fool with money on my mind\n", "Got my ten in my hand and a gleam in my eye\n", "I'm a loc'd out gangsta, set tripping banger\n", "And my homies is down, so don't arouse my anger\n", "Fool, death ain't nothing but a heart beat away\n", "I'm living life do or die, what can I say?\n", "I'm 23 now but will I live to see 24?\n", "The way things is going I don't know\n", "Tell me why are we so blind to see\n", "That the ones we hurt are you and me?\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Power and the money, money and the power\n", "Minute after minute, hour after hour\n", "Everybody's runnin', but half of them ain't looking\n", "It's going on in the kitchen, but I don't know what's cooking\n", "They say I gotta learn, but nobody's here to teach me\n", "If they can't understand it, how can they reach me?\n", "I guess they can't, I guess they won't\n", "I guess they front, that's why I know my life is out of luck, fool\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Been spending most their lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Keep spending most our lives\n", "Living in a gangsta's paradise\n", "Tell me why are we so blind to see\n", "That the ones we hurt are you and me?\n", "Tell me why are we so blind to see\n", "That the ones we hurt are you and me?\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "bd98b06c", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "bd98b06c", "outputId": "ec17e09f-49a3-485d-f982-eb7b388be085" }, "outputs": [], "source": [ "sw_compare(coolio_gangtas_paradise, stevie_wonder_pastime_paradise, base_similarity)" ] }, { "cell_type": "code", "execution_count": null, "id": "00a5d4d4", "metadata": { "id": "00a5d4d4" }, "outputs": [], "source": [ "kjv_bible_proverbs23 = \"\"\"The Lord is my shepherd; I shall not want. He maketh me to lie down in green pastures: he leadeth me beside the still waters. He restoreth my soul: he leadeth me in the paths of righteousness for his name’s sake. Yea, though I walk through the valley of the shadow of death, I will fear no evil: for thou art with me; thy rod and thy staff they comfort me. Thou preparest a table before me in the presence of mine enemies: thou anointest my head with oil; my cup runneth over. Surely goodness and mercy shall follow me all the days of my life: and I will dwell in the house of the Lord for ever.\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "0288124d", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "0288124d", "outputId": "a9132d51-9371-4c14-8226-7b983e943420" }, "outputs": [], "source": [ "sw_compare(coolio_gangtas_paradise, kjv_bible_proverbs23, base_similarity)" ] }, { "cell_type": "code", "execution_count": null, "id": "5a0b4da8", "metadata": { "id": "5a0b4da8" }, "outputs": [], "source": [ "wolf_killing_floor = \"\"\"I should'a quit you, a long time ago\n", "I should'a quit you, baby, long time ago\n", "I should'a quit you, and went on to Mexico\n", "\n", "If I ha'da followed my first mind\n", "If I ha'da followed my first mind\n", "I'd'a been gone since my second time\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "ddcf1467", "metadata": { "id": "ddcf1467" }, "outputs": [], "source": [ "led_zeppelin_lemon_song = \"\"\"I should have quit you a long time ago\n", "Ooh - whoa, yeah, yeah, long time ago\n", "I wouldn't be here, my children\n", "Down on this killin' floor\n", "I should have listened, baby, a - to my second mind\n", "Oh, I should have listened, baby, to my second mind\"\"\"" ] }, { "cell_type": "code", "execution_count": null, "id": "b065424c", "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "b065424c", "outputId": "021b5910-793f-4e7b-9f5e-aebce44f9af3" }, "outputs": [], "source": [ "sw_compare(wolf_killing_floor, led_zeppelin_lemon_song, base_similarity)" ] }, { "cell_type": "markdown", "id": "74cac635", "metadata": { "id": "74cac635" }, "source": [ "The `base_similarity` method above calculates a very coarse measure of similarity, only testing whether two words are exactly the same. At this point in the course, you have many more methods in your toolbox for thinking about the similarity of two tokens in a sentence. Can you develop a better similarity function (`better_similarity`) that captures what you see as the important dimensions of text reuse in these examples?" ] }, { "cell_type": "code", "execution_count": null, "id": "c850ce4f", "metadata": { "id": "c850ce4f" }, "outputs": [], "source": [ "def better_similarity(token1, token2):\n", " # fill in here\n" ] }, { "cell_type": "code", "execution_count": null, "id": "7a24330e", "metadata": { "id": "7a24330e" }, "outputs": [], "source": [ "sw_compare(coolio_gangtas_paradise, stevie_wonder_pastime_paradise, better_similarity)" ] }, { "cell_type": "code", "execution_count": null, "id": "8f4526d2", "metadata": { "id": "8f4526d2" }, "outputs": [], "source": [ "sw_compare(coolio_gangtas_paradise, kjv_bible_proverbs23, better_similarity)" ] }, { "cell_type": "code", "execution_count": null, "id": "301dd2a3", "metadata": { "id": "301dd2a3" }, "outputs": [], "source": [ "sw_compare(weird_al_eat_it, jackson_beat_it, better_similarity)" ] }, { "cell_type": "code", "execution_count": null, "id": "3088eb44", "metadata": { "id": "3088eb44" }, "outputs": [], "source": [ "sw_compare(wolf_killing_floor, led_zeppelin_lemon_song, better_similarity)" ] } ], "metadata": { "colab": { "provenance": [] }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.11.14" } }, "nbformat": 4, "nbformat_minor": 5 }