CSCI-570 Spring 2025

Analysis of Algorithms

Final Project

Due: May 12, 2025

1    Guidelines

You can work on this project in groups of no more than 3 people.

2    Project Description

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

2.1    Algorithm Description

Suppose we are given two strings X and Y , where X consists of the sequence of symbols x1 , x2 , . . . , xm and Y consists of the 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 of these two sets is an alignment if there 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 of X or Y that is not matched in M — it is a gap — we incur a cost of δ .

2.  Second, for each pair of letters p, 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 αxi yj    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.

3.  The cost of M is the sum of its gap and mismatch costs, and we seek an alignment of minimum cost.

2.2    Input string Generator

The input to the program would be a text file containing the following information:

1.  First base string (s1 )

2.  Next j lines consist of indices after which the copy of the previous string needs to be inserted in the cumulative string.  (eg given below)

3.  Second base string (s2 )

4.  Next k lines consist of indices after which the copy of the previous string needs to be inserted in the cumulative string.  (eg given below)

This information would help generate 2 strings from the original 2 base strings.  This file could be used as an input to your program, and your program could use the base strings and the rules to generate the actual strings.  Also note that the numbers j  and k correspond to the first and the second string, respectively. Make sure you validate the length of the first and the second string to be 2j  * len(s1 ) and 2k  * len(s2 ).  Please note that the base strings need not be of equal length and similarly, j need not be equal to k.

Example:

ACTG

3

6

1

TACG 1

2

9

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

2.3    Values for Delta and Alphas

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

2.4    Programming/Scripting Languages

Following are the list of languages which could be used:

1.  C

2.  C++

3.  Java

4.  Python

5.  Python3

2.5    Bounds

1.  Basic Algorithm

•  0 ≤ j, k ≤ 10

•  1 ≤ len(s1 ), len(s2 ) ≤ 2000

•  1 ≤ 2j  * len(s1 ), 2k  * len(s2 ) ≤ 2000

2.  Memory Efficient Algorithm

•  0 ≤ j, k ≤ 20

•  1 ≤ len(s1 ), len(s2 ) ≤ 20000

•  1 ≤ 2j  * len(s1 ), 2k  * len(s2 ) ≤ 20000

3    Goals

Following are the goals to achieve for your project:

3.1

Your program should take 2 arguments:

1. Input file path

2.  Output file path (If path is valid and file not found, your program should create it) Examples:

python2  basic_2.py  input .txt  output .txt java  Basic  input .txt  output .txt

python3  basic_3.py  input .txt  output .txt

Note: As mentioned in Part II-B input file will have data to generate strings.  Since Gap penalty (δe ) and Mismatch penalty (αpq ) are FIXED, you have to hardcode them in your program.

You are not allowed to use any libraries.

3.2

Implement the Dynamic Programming algorithm. Your program should print the following information at the respective lines in the output file:

1.  Cost of the alignment (Integer)

2.  First string alignment ( Consists of A, C, T, G,   (gap) characters)

3.  Second string alignment ( Consists of A, C, T, G,   (gap) characters )

4.  Time in Milliseconds (Float)

5.  Memory in Kilobytes (Float)

Note:  There  can be multiple alignments that have the same cost.  You can print ANY alignment generated by your program. The only condition is it should have a minimum cost.

e.g. For strings s1 : A and s2 : C, alignments A   ,   C and   A, C   both have alignment cost 60 which is minimum. You can print any one of them.

3.3

Implement the memory-efficient version of this solution and repeat the tests in Part B.

3.4

Plot the results of Part B and Part C using a line graph.

Please  use the  provided  input  files  in the  ‘datapoints’  folder  for  generating the  data points to plot the graph.

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

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

Units: CPU time - milliseconds, Memory in KB, problem size m+n

4    Submission

4.1

You should submit the ZIP file containing the following files:

a.  Basic algorithm file

Name of the program file should be ‘basic.c’ / ‘basic.cpp’ / ‘Basic.java’ / ‘basic   2.py’ (Python 2.7) / ‘basic 3.py’ (Python 3)

b.  Memory efficient algorithm file

Name of the program file should be ‘efficient.c’ / ‘efficient.cpp’ / ‘Efficient.java’ / ‘efficient   2.py’(Python

2.7) / ‘efficient 3.py’ (Python 3)

c.  Summary.pdf

It must contain the following details:

1.  Datapoints output table (which are generated from provided input files)

2.  Two graphs and Insights

3.  Contribution from each group member e.g. coding, testing, report preparation, etc. if every- body did not have equal contribution (Please use the provided Summary.docx file, fill in the details and upload it as PDF)

d.  2 Shell files ‘basic.sh’ and  ‘efficient.sh’ with the commands to compile and run your basic and efficient version. These are needed to provide you with flexibility in passing any additional compil- er/run arguments that your programs might need. See More Hints (VII part E for more details)

Example: basic .sh

javac  Basic.java

java  Basic  "$1"  "$2"

Execution:  ./basic .sh  input .txt  output .txt

./efficient .sh  input .txt  output .txt

4.2

The name of your zip file should have the USC IDs (not email ids) of everyone in your group separated by an underscore. e.g.

•  1234567890   1234567890   1234567890.zip

•  Contents (example):

1234567890_1234567890_1234567890

-  basic_2.py

-  efficient_2.py

-  Summary.pdf

-  basic .sh

-  efficient .sh

5    Grading

Please read the following instructions to understand how your submission will be evaluated.

5.1    Correctness of algorithms - 70 points

1.  Both programs (basic/ efficient) are correctly outputting files having all 5 lines in the correct order:

15 points

2.  Basic Algorithm: 25 points

3.  Memory Efficient Algorithm: 30 points

Note: Graders will execute your program on the ‘Linux‘ OS. The goal of Part A is to check correctness.

The program should output a valid alignment having a minimum cost.   Memory  and  Time  will be evaluated in Part B.

5.2    Plots, analysis of results, insights and observations:  30 points

1. Your program will be run on the input files (provided by us in the ‘data points’ folder) to generate output files. The memory and time in the output files should be in a “close range” to what is given by you in the Summary.pdf.

2.  Correctness of the graph

3.  Correctness of Analysis/ Insights

Note: Unlike Part A, the evaluation of Part B is subjective so it will be done manually.  So it is alright if your graphs/data points have ‘some’ outliers.

6    What is provided to you in the zip file?

A.  SampleTestCases folder containing sample input and output files

B.  Datapoint folder containing input files to generate graph data points.

C.  Summary.docx file for reference

7    HINTS, NOTES, and FAQs

7.1    Regarding Input and string generation

1. We will never give an invalid input to your program. Input strings will always contain A, C, G, T only.

2.  The length of the final input string should be equal to 2number of lines *len(base string), as mentioned in the document.

3.  The string generation mechanism is the same irrespective of the basic or the efficient version of the algorithm.

4.  The entire program (string generation, solution, write output) should be written in a single file. You may break those functions into different classes to make the code modular, but there should be only one file. Your program won’t be evaluated based on how modular it is.

7.2    Regarding Algorithm and output

1.  DO NOT REFER TO THE PSEUDOCODE PROVIDED IN KLEINBERG AND TARDOS.

2.  DO NOT USE ANY LIBRARIES FOR WRITING YOUR ALGORITHMS.

3.  Samples for time and memory calculation are provided. Please use them for consistency.

4. Your solutions for the regular and memory-efficient algorithms should be in two different programs.

5.  There can be multiple valid sequences with the same optimal cost; you can output any of those. All of them are valid.

6. You should code both the basic version and memory-efficient algorithm.  Even though the memory- efficient version will pass all the bounds of the simple version, you must not use the memory-efficient version in both sub-problems.

7. Your program should not print anything when it runs. It should only write to the output file.

8.  There is no specific requirement for the precision of Time and Memory float values.

9.  Time and Memory depend on so many factors such as CPU, Operating System, etc.  So there might be differences in the output.  Therefore, it will be evaluated subjectively.  There must be a clear distinction in behavior between programs whose Time/ Memory complexity is O(n) vs O(n2 ) vs O(log n).

7.3    Regarding the plot

1.  Both the graphs are line graphs.  The X-axis represents problem size as m+n, where m and n are the lengths of the generated string, and the Y-axis of the Memory plot represents memory in KB, and the Y-axis of the Time Plot represents time in milliseconds.  The 2 lines in the graph will represent stats of basic and memory-efficient algorithms.

2. You can use any libraries/packages in any language to plot the graphs.

3. You do not have to provide code for generating the plots. Only add images in the Summary.pdf.

7.4    Regarding Submission

1.  Only 1 person in the group needs to submit the project.  We’ll get the USC IDs of all the other team members from the filenames.

2.  To allow for grading the whole class in a reasonable amount of time, we’ll kill your program if it runs for more than a minute on a single input file.