You will find on UMLearn, under Content / Assignments / Assignment 1, the complete ge-

nomic sequence of Sorangium cellulosum So ce56 in fasta format (Sorangium cellulosum.fasta) . You have to submit on UMLearn before Oct 4th, at 5 pm:

❼ your code;

❼ a text file containing the answers to the questions asked at the end of this document (see section 5).

This assignment can be completed individually or in a team of (no more than) 2. If you choose to work as a team of 2, only one submission on UMLearn  (by one member of the team) is required, but you have to put both names in the code (commented at the beginning of the file) and also in the text file.

The online academic honesty declaration checklist has to be completed on UMLearn to submit this assignment (otherwise the submission folder will be invisible).

1    Introduction

This assignment will focus on the problem of multiple pattern matching (set matching). You will be asked to implement two approaches for this problem, and run some tests to compare their speed.  The genome that is provided to you is one of the largest bacterial genomes that has been fully sequenced to date, with a single unichromosomal genome of about 13 Mbp (million base pairs).

The key in this assignment is not only to implement the required algorithms correctly, but also (reasonably) optimally.  Dealing with a very large input might be a new experience for you.  As you will see, large inputs are less forgiving in terms of code optimization than smaller inputs that you might have dealt with in previous courses.  That means that a seemingly small operation in your code that gets executed for every input character could increase the runtime significantly on a large input.  In other words,  an algorithm that is supposed to be faster in theory could run slower than a more naive approach if implemented poorly.

Note that marks can be taken off in this (and future) assignments for algorithms that are clearly not optimal in their implementation.

Please consult the slides on  “Python review” posted in the Assignments module to famil- iarize yourselves with some useful Python tools and modules (e.g. BioPython).

2    Implementing the  brute-force  exact  pattern  matching  algo- rithm generalized to multiple patterns (2 points)

Implement the naive brute-force approach seen in class (sliding window approach), but generalized to the problem of set matching.  In other words, your implementation should be able to search for all the occurrences of a given list of patterns in the input DNA sequence.  You can implement this in a simple function that receives two parameters:  a list of patterns and a sequence.  It should output the number of matches found for each pattern in the list.

3    Implementing Aho-Corasick (5 points)

Implement the Aho-Corasick algorithm, as presented in class.  Your program must start by doing the pre-processing, which involves building the complete trie (prefix tree) with go-to, fail and output arcs/functions. There are many ways to accomplish this, but using objects is probably a good strategy here.  Note that the alphabet of the provided DNA sequence is {A,C,G,T}.

Once the pre-processing is done, implement a method that will do the search (of all input patterns) using the trie.  This just boils down to implementing the pseudocode shown on slide 135 of the notes of week 2 (“3-Exact pattern matching”).  It should output the number of matches found for each pattern in the list.

4    Program input/output and code quality/readability (1 point)

Your program must accept as command-line parameters:

❼ a filename (the fasta file) – this must come first, before the list of patterns

❼ a list of patterns to search for (list must have at least one pattern)

❼ -b: an optional parameter determining which algorithm to use:  by default (without this parameter), the Aho-Corasick algorithm will be used, and when -b is added, the brute-force algorithm will be used

Your program will then use the corresponding algorithm to find the number of occurrences of the given patterns in the forward strand (only) of the input fasta file (the sequence in the file represents the forward strand).

Your program will also calculate and output how much time is needed to find all the matches.  You can import the  “time” module (import  time) and use the time. time() method to get a time stamp.  You can include the time that is needed to complete the pre-processing, although that should be negligible.

To help you, here is how to run the program and the expected output  (please try to match this output format) when searching for patterns AAA and AAAA in the file So- rangium cellulosum.fa, using the brute-force approach1 :

Here is the same search done using the Aho-Corasick algorithm:

In terms of code quality and readability, we do not have specific programming standards in this course, but you should do your best to follow good programming practices that you have seen in previous courses.  Marks can be taken off for code that is poorly writ- ten/organized and hard to follow/understand.