{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\def\\CC{\\bf C}\n", "\\def\\QQ{\\bf Q}\n", "\\def\\RR{\\bf R}\n", "\\def\\ZZ{\\bf Z}\n", "\\def\\NN{\\bf N}\n", "$$\n", "# Strings and the Burrows-Wheeler Transform\n", "\n", "Authors \n", "- Franco Saliola\n", "\n", "License \n", "CC BY-SA 3.0\n", "\n", "Sage/Python includes a builtin datastructure for strings. There are\n", "several ways to input strings. You can input a string using single\n", "quotes `'` or double quotes `\"` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = \"This is a string!\"\n", "s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = 'So is this!'\n", "print(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can also input a string using three quotes (`\"\"\"` or `'''`). This is\n", "useful if you want to use both `\"` and `'` in your string, or you want\n", "your string to span multiple lines:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = \"\"\"\n", "This is a multi-line\n", " string\n", "that includes 'single quotes'\n", " and \"double quotes\".\n", "\"\"\"\n", "print(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Create and print the following string." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ " \\ | ( | ) / /\n", "_________________\n", "| |\n", "| |\n", "| I <3 Coffee! /--\\ \n", "| | |\n", " \\ /\\--/\n", " \\___________/" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Without using cut-and-paste(!) *replace* the substring **I\n", "<3 Coffee!** with the substring **I <3 Tea!**." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Print a copy of your string with all the letters\n", "capitalized (uppercase)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Strings behave very much like lists. For example,\n", "\n", "| | | |\n", "|--------------------|------------------------|----------------------|\n", "| **Operation** | **Syntax for strings** | **Syntax for lists** |\n", "| Accessing a letter | `string[3]` | `list[3]` |\n", "| Slicing | `string[3:17:2]` | `list[3:17:2]` |\n", "| Concatenation | `string1 \\+ sting2` | `list1 \\+ list2` |\n", "| A copy | `string[:]` | `list[:]` |\n", "| A reversed copy | `string[::\\-1]` | `list[::\\-1]` |\n", "| Length | `len(string)` | `len(list)` |\n", "\n", "**Exercise:** The *factors* of length 2 of 'rhubarb' are\n", "\n", "- hu\n", "- ub\n", "- ba\n", "- ar\n", "- rb\n", "\n", "Write a function called `factors(s, l)` that returns a list of the\n", "factors of length `l` of `s`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Using your `factors` function list all the factors of\n", "length 3 of `'rhubarb'`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** What happens if you apply your function `factors` to the\n", "list `[0,1,1,0,1,0,0,1]`? If it doesn't work for both lists and strings,\n", "go back and modify your function so that it does work for both." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "------------------------------------------------------------------------\n", "\n", "## Run-length encoding\n", "\n", "The string\n", "\n", "> **WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW**\n", "\n", "begins with **W** 12 times, then **B** once, then **W** 12 times, then\n", "**B** 3 times, then **W** 24 times, then **B** once and then **W** 14\n", "times. Thus, it can be encoded as\n", "\n", "> **(W, 12), (B, 1), (W, 12), (B, 3), (W, 24), (B, 1), (W, 14)**.\n", "\n", "This is called the *run-length encoding* of the string.\n", "\n", "**Exercise:** Write a function `run_length_encoding(s)` that returns the\n", "run-length encoding of a string `s`. Does your function work for lists\n", "as well as strings? If not, then can you make it so that it works for\n", "both strings and lists? Use your function to compute the run-length\n", "encoding of the following list." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "l = [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,\n", "0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Rotations\n", "\n", "The *rotations* of the string 'bananas' are:\n", "\n", "- ananasb\n", "- nanasba\n", "- anasban\n", "- nasbana\n", "- asbanan\n", "- sbanana\n", "\n", "and if we sort these alphabetically, then we get:\n", "\n", "- anasban\n", "- asbanan\n", "- bananas\n", "- nanasba\n", "- nasbana\n", "- sbanana\n", "\n", "**Exercise:** Define a function `print_sorted_rotations(s)` that sorts\n", "all the rotations of a string and prints them in an array as above.\n", "Print the sorted rotations of the strings `'ananas'` and `'cocomero'`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "------------------------------------------------------------------------\n", "\n", "## The Burrows-Wheeler Transform\n", "\n", "The *Burrows-Wheeler Transform* (BWT) of a string **s** sorts all the\n", "rotations of **s** and then returns the last column.\n", "\n", "For example, if we sort the rotations of 'bananas':\n", "\n", "- ananasb\n", "- anasban\n", "- asbanan\n", "- bananas\n", "- nanasba\n", "- nasbana\n", "- sbanana\n", "\n", "then the last column is *bnnsaaa* , so the BWT of *bananas* is *bnnsaaa*\n", ".\n", "\n", "**Exercise:** Write a function `bwt(s)` that returns the BWT of the\n", "string `s`. Compute the BWT of *bananas* , *ananas* and *cocomero* . (\n", "*Hint:* You can return your answer as a list, but if you want to return\n", "a string, then you might want to use the `.join()` method for strings.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "------------------------------------------------------------------------\n", "\n", "**Exercise:** Combine the functions you defined above to create an\n", "`@interact` object that takes a string `s` and prints:\n", "\n", "- the sorted rotations of `s`\n", "- the run-length encoding of `s`\n", "- the BWT of `s`\n", "- the run-length encoding of the BWT of `s`\n", "\n", "(*hint:* String formatting can be done using the `%` operator. Here are\n", "some examples:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print('The sum of %s and %s is %s.' % (3,2,3+2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If you are familiar with the *C* language then you will notice that\n", "string formating is very similar to *C* 's *printf* statement.)\n", "\n", "Use your interact object to explore this transformation, and then to\n", "answer the following questions below.\n", "\n", "**Exercise:** What is the BWT of the three following strings?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 = 'xxyxyxyxyxyxyxyxyxxyxyxyxyxyxyxyxyxy'\n", "s2 = '01101001100101101001011001101001100101100110100101'\n", "s3 = 'cdccdcdccdccdcdccdcdccdccdcdccdccdcdccdcdccdccdcdc'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Do you notice any patterns in the BWT of a string?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Can you think of an application for this transformation?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Find 3 other strings that have a 'nice' image under the BWT." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Is the Burrows-Wheeler transformation invertible? (That\n", "is, can you find two strings that have the same BWT?)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** By comparing the BWT of a string with the first column of\n", "the array of sorted rotations of a string `s`, devise and implement an\n", "algorithm that reconstructs the first column of the array from the BWT\n", "of `s`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** By examining the first *two* columns of the array, devise\n", "and implement an algorithm that reconstructs the first *two* columns of\n", "the array from the BWT of a string." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(*hint:* compare the last and first column with the first two columns.)\n", "\n", "**Exercise:** By examining the first *three* columns of the array,\n", "devise and implement an algorithm that reconstructs the first *three*\n", "columns of the array from the BWT of a string." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Write a function that reconstructs the entire array of\n", "sorted rotations of a string from the BWT of the string." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** A *Lyndon word* is a word w that comes first in\n", "alphabetical order among all its rotations. Is the BWT invertible on\n", "Lyndon words?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise:** Explain how one can modify the BWT to make it invertible\n", "on arbitrary words. Implement your modified transformation and the\n", "inverse transformation." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# edit here" ] } ], "metadata": { "kernelspec": { "display_name": "sagemath", "name": "sagemath" } }, "nbformat": 4, "nbformat_minor": 2 }