CSE 494/559: Algorithms in Computation Bio

Description

Note that any program you implement should run within 5 mins (wall time) to produce an output to be
satisfactory.

Multiple Pattern Matching
In this section of the assignment, your end goal is to implement pattern matching based on Burrows-
Wheeler Transform. In order to achieve this end goal, there are several smaller modules that you will need
to implement.
1. [Computing BWT of a string] In short, BWT is the last column of Burrows-Wheeler
Matrix (BWM), where BWM is produced by sorting the collection of every cyclic rotation of the given
string. Write a program that computes BWT of an input string. The special symbol ‘$’ comes before
any permitted alphabet.

Input: A string s ending with ‘$’
Output: BWT of s

Sample input file content
panamabananas$

Sample output:
smnpbnnaaaaa$a

2. [Computing the original string of a given BWT] BWT is a reversible permutation of a
given string. Write a program that computes the original string of a given BWT.

Input: A string t (Note that t contains a single occurrence of ‘$

Output:The original string of BWTt

Sample input file content
smnpbnnaaaaa$a

Sample output:
panamabananas$

3. [Compute the LF mapping] In Burrows-Wheeler Matrix (BWM), there is a LF mapping
property where the ith occurence of a character c ∈ Σ in the last column (BWT) of BWM and ith
occurence of c in the first column of BWM correspond to the same occurrence in the original string
used to construct BWM and BWT. Write a program that computes the index of a corresponding
character in the first column to the character at a given index in the last column.

Input: BWT of a string (last column of BWM) and an index number for a position on BWT.

Output: The corresponding index position for the first column in BWM to the input index i according
to the LF mapping property.

Sample input file content
smnpbnnaaaaa$a
2

Sample output:
9

4. [Burrows-Wheeler Matching Algorithm] Recall that Burrwos-Wheeler matching algo-
rithm matches symbols in the pattern from right-to-left by using LF mapping repeatedly to narrow
down the ranges in BWM similar to binary search procedures done in Suffix Array. Write a program
that performs Burrows-Wheeler matching

Input: Given a string (BW T ) and a list of patterns.
Output: For each input pattern, output the number of times the pattern appears in the original text

Sample input file content
smnpbnnaaaaa$a
ana na nam nas nab

Sample output:
3 3 1 1 0

Testcases:

For each question, 3 test cases for debugging and 1 test case for submission are included.

1_compute_BWT_of_a_string.zip (Uploaded)

2_compute_original_string_given_BWT.zip (Uploaded)

3_compute_LF_mapping.zip (Uploaded)

4 _BWM_algo.zip (Uploaded)

What and how to submit:

FOLLOW THESE INSTRUCTIONS SO THAT AUTOGRADER CAN RUN SMOOTHLY AGAINST YOUR SOLUTIONS:

1. Submit your source codes ONLY. Everything should be at root level. Don’t create folder structures. Submit them on gradescope.

2. Name the files as q{question_num}.file_ext (e.g., q1.py, q2.cpp).

3. Input files will follow the format test_{i}.txt (e.g., test_1.txt) [ These file names must be taken as arguments to your programs ]

4. Output files should follow the format sol_q{question_num}_t{testcase_num}.txt (e.g., sol_q1_t1.txt).

5. The test case ‘test_{i}.txt’ will be put under the same directory as your source codes. Make sure your code will compile, run, read the ‘test_{i}.txt’ automatically, and write your outputs into a txt file under the same directory.

6. Files will be run the following way.

ex: For python, python3 q1.py test_1.txt

7. If you have any external packages, add them in a requirements.txt file and upload.

We will run your code by

python q1.py (for python)

javac q1.java

java q1 (for java)

g++ q1.cpp -o q1

./q1 (for c++)

If you are using other programming languages, please name your source code in a similar way and include an additional README file to describe how to run your code.

If you are using other programming languages, please name your source code in a similar way and include an additional README file to describe how to run your code.