CSCI-570 Fall 2021

Analysis ofAlgorithms

Final Project

I.     Guidelines

The project is related to the implementation of the two different solutions provided in chapter 6 of the Kleinberg textbook for the Sequence Alignment problem. You can work on this project in groups of no more than 3 people.

II.     Project Description

Implement the basic Dynamic Programming solution to the Sequence Alignment problem. Run the test set provided and show your results.

A. Algorithm Description:

Suppose we are given two strings X and Y, where X consists ofthe sequence of symbols   x1, x2 . . . xm and Y consists ofthe sequence of symbols y1, y2 . . . yn . Consider the sets {1,    2, . . . , m} and {1, 2, . . . , n} as representing the different positions in the strings X and Y, and consider a matching of these sets; recall that a matching is a set of ordered pairs with  the property that each item occurs in at most one pair. We say that a matching M ofthese  two sets is an alignment ifthere are no “crossing” pairs: if (i,j), (i’ ,j’) ∈ M and i < i’ ,  then j <j’ . Intuitively, an alignment gives a way of lining up the two strings, by telling   us which pairs of positions will be lined up with one another.

Our definition of similarity will be based on finding the optimal alignment between X and Y, according to the following criteria. Suppose M is a given alignment between X and Y:

1.   First, there is a parameter δe  > 0 that defines a gap penalty. For each position ofX or Y that is not matched in M — it is a gap — we incur a cost of δ .

2.   Second, for each pair of lettersp, q in our alphabet, there is a mismatch cost of αpq for lining up p with q. Thus, for each (i,j) ∈ M, we pay the appropriate mismatch cost αxiyj  for lining up xi with yj . One generally assumes that αpp  = 0 for each letter p—there is no mismatch cost to line up a letter with another copy of                      itself—although this will not be necessary in anything that follows.

Using the above numbers, the generated strings would be

ACACTGACTACTGACTGGTGACTACTGACTGG and

TATTATACGCTATTATACGCGACGCGGACGCG

Following is the step by step process on how the above strings are generated.

ACTG

ACTGACTG

ACTGACTACTGACTGG

ACACTGACTACTGACTGGTGACTACTGACTGG

TACG

TATACGCG

TATTATACGCGACGCG

TATTATACGCTATTATACGCGACGCGGACGCG

C. Values for Delta and Alphas

Values for α’s are as follows. δe  is equal to 30.

D. Programming/Scripting Languages:

Following are the list of languages which could be used:

1.   C

2.   C++

3.   Java

4.   Python

5.   Python3

E. Bounds:

Bounds on the length of the base strings and the values of m and n, along with the zip file will be released on 17 November 2021, i.e. 3 weeks before the due date.

III.     Goals

Following are the goals to achieve for your project

A. Your program should take input:

1.   2 strings that need to be aligned, should be generated from the string generator mentioned above.

2.   Gap penalty (δe).

3.   Mismatch penalty (αpq).

B. Your solution should output output.txt file containing the following information at the respective lines:

1.   The first 50 elements and the last 50 elements ofthe actual alignment.

2.   The time it took to complete the entire solution.

3.   Memory required.

C. Implement the memory efficient version ofthis solution and repeat the tests in Part B.

D. Plot the results ofPart A and Part B:

1.   Single plot of CPU time vs problem size for the two solutions.

2.   Single plot ofMemory usage vs problem size for the two solutions.

IV.     Notes and Hints

A. You will be provided a zipfile which has a folder containing some sample test     cases and corresponding output text files containing the correct answers. Please  note that we will be having another set of test cases (that are not released) which will be used for testing your program/script.

B. You should provide us with a zipfile containing your programs/scripts along with plots and a summary file.