CSCI-570-Final Project

On Sale

$25.00

Added to cart

The project is on the implementation of the two different solutions discussed in class for the Sequence Alignment problem. You can work in groups of 3 people or less. Plagiarism of any kind will be strictly monitored & reported as violation of academic integrity.

Project Description

Implement the two solutions to the Sequence Alignment problem - the basic version using Dynamic programming, and the memory efficient version which combines DP with Divide-n-conquer. Run the test set provided and show your results.

Problem review

Suppose we are given two strings and , where consists of the sequence of symbols ₁ , ₂ , ... , _m and consists of the sequence of symbols ₁ , ₂ , ... , _n. Consider the sets {1, 2, ... , } and {1, 2, ... , } as representing the different positions in the strings and , 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 of these two sets is an alignment if there are no “crossing” pairs: for ( , ), ( ', ') ϵ if < ' , then < '. 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.

The similarity between and is based on the optimal alignment between and . Suppose is a given alignment between and :

First, there is a parameter δ > 0 that defines a gap penalty. Each position of or that is not matched in is a gap, and we incur a cost of δ for it.

Second, for each pair of letters , in our alphabet, there is a mismatch cost of α_pq for matching with . Thus, for each ( , ) ϵ , we pay the appropriate mismatch cost α_pq where p = x_i and q = x_j. One generally assumes that α_pp = 0 for each letter —there is no mismatch cost to line up a letter with another copy of itself—although this assumption will not be necessary in anything that follows.
Finally, the cost of is the sum of all of its gap and mismatch costs, and we seek an alignment having the minimum cost.

Input string Generator

In order to potentially work with long strings as test inputs, we use a string generation method. Thus, any input to the program would be generated using a provided text file as follows:

First line has a base string - let’s call it ₀.

Next lines consist of numbers that correspond to j steps we execute iteratively, each generating a new string, say strings ₁, s₂, …, s_j , across the j steps, as follows. In step 1, we take the given integer n₁ in line 1 (among the j lines), and insert a copy of ₀ within itself, right after its index n₁ (assuming 0-indexing). This gives us the string s₁. Then, in step 2, we see the integer n₂ in line 2, and insert s₁ within itself right after its index n₂, giving us string s₂. Repeating this for j steps gives us s_j which is the first string in our input for the alignment problem. Note that each step doubles the length of the string generated, thus, len(s_j) = 2^j * len(s₀). See an illustrative example given below.

The subsequent lines contain a base string t₀ followed by k lines each containing a number. We use them as above to iteratively generate strings t₁, t₂, …, t_k, with t_k being the second string input for the alignment problem.

Thus, this text file could be used as an input to your program and your program should use the generation method above to get the actual input strings to be aligned. Note that need not equal for the string generation shown above. Consider the following input as example: ACTG

TACG

Following is the step by step process on how the final two strings are generated. First base string: ACTG

Insertion after index 3: ACTGACTG

Insertion after index 6: ACTGACTACTGACTGG

Insertion after index 1:ACACTGACTACTGACTGGTGACTACTGACTGG

Similarly,

TACG

TATACGCG

TATTATACGCGACGCG

TATTATACGCTATTATACGCGACGCGGACGCG

Thus, using the inputs above, the generated strings are ACACTGACTACTGACTGGTGACTACTGACTGG and TATTATACGCTATTATACGCGACGCGGACGCG which now need to be aligned.

Values for Delta and Alphas

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

110

118

110

Programming/Scripting Languages

Following are the list of languages which could be used:

Java

Python2

Python3
Bounds

Basic Algorithm 0<= , <=10

1 <= ( ₀), (t₀) <= 2000

The values will also ensure that 1 <= ( _j), (t_k) <= 2000

Memory Efficient Algorithm

0<= , <=20

1 <= ( ₀), (t₀) <= 20000 1 <= ( _j), (t_k) <= 20000

Final output and submission format

A. Your program should take 2 arguments

input file path

output file path (If path is valid and file not found, your program should create it)

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

You are not allowed to use any libraries that may be directly applicable to sequence alignment problem.

Implement the basic version of the solution. Your program should print the following information at the respective lines in output file:

Cost of the alignment (Integer)

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

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

Time in Milliseconds (Float)

Memory in Kilobytes (Float)

Note: There can be multiple solutions which have the same cost. You can print ANY of them as generated by your program. The only condition is, it should have a minimum cost.

E.g., For strings A and C, alignments A_, _C and _A, C_ both have

alignment cost 60 which is minimum (indeed, in this case, they represent the same matching in two different ways). You can print any one of them.

Implement the memory efficient version of this solution and repeat the tests as in Part B and produce output in the same format.

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.)

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

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

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

Submission

You should submit the ZIP file containing the following files.

Basic algorithm file

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

Memory efficient algorithm file

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

Summary.pdf

It must contain following details

datapoints output table (which are generated from provided input files)
Two graphs and your insights from them

Contribution from each group member, e.g., coding, testing, report etc. if everyone did not have equal contribution.

(Please use the provided Summary.docx file, fill in the details and upload it as PDF)

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 flexibility in passing any additional compiler/run arguments that your programs might need. See More Hints (VII part E for more details)

basic.sh

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

./efficient.sh input.txt output.txt

The name of your zip file should have the USC IDs (not email ids) of everyone in your group separated by underscore. The zip file structure will look like

1234567891_1234567892_1234567893.zip

1234567891_1234567892_1234567893

basic_2.py

efficient_2.py

Summary.pdf

basic.sh

efficient.sh

IV. Grading

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

Correctness of algorithms - 70 points

Both programs (basic/ efficient) are correctly outputting file having all 5 lines in correct order: 15 points

Basic Algorithm: 25 points

Memory Efficient Algorithm: 30 points

Note: The goal of Part A is to check the correctness of alignment having minimum cost. Memory and Time will be evaluated in Part B.

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

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 reasonably match what you submitted in the Summary.pdf
Correctness of the graph

Correctness of analysis/ insights

Note: Unlike Part A, evaluation of Part B is subjective so it will be done manually.

So it is alright if your graphs/data points have ‘some’ outliers etc.

What is provided to you in the zip file?

SampleTestCases folder containing sample input and output files

Datapoint folder containing files to generate graph data points.

Summary.docx file as template

VI. HINTS, NOTES, and FAQs

Regarding Input and string generation

We will never give an invalid input to your program. Input strings will only contain A, C, G, T. The insertion indices in the input will be valid numbers.

The string generation mechanism is the same irrespective of the basic or the efficient version of the algorithm.
The entire program (string generation, solution, write output) should be written in a single file. You may break those functions in different classes to make the code modular, but there should be only one file for consistency of submissions.

Regarding Algorithm and output

We strongly recommend to refer to lecture slides for the algorithm overview, and

NOT THE PSEUDOCODE PROVIDED IN KLEINBERG AND TARDOS textbook. In our prior experience, students opting for the latter reported lots of difficulties in implementation.

DO NOT USE ANY LIBRARIES FOR WRITING YOUR ALGORITHMS barring the standard ones. If you are really unsure, ask us on piazza.
Samples for time and memory calculation are provided. Please use them for consistency.
Your solutions for the regular and memory-efficient algorithms should be in two different programs.
There can be multiple valid sequences with the same optimal cost, you can output any of those. All of them are valid.
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 of the sub-problems, otherwise the plots will not show the expected distinctions.

Your program must not print anything when it runs, only write to the output file.

There is no specific requirement for the precision of Time and Memory float values.
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(n²) vs O(logn) etc.

Regarding the plot

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

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

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

Regarding Submission

Only 1 person in the group should submit the project. We will get the USC IDs of all the other team members from the filenames.
To allow for grading the whole class in a reasonable amount of time, we will kill your program if it is stuck on a single input file for long (~few minutes).
Regarding Shell File

To make the evaluation seamless on our end, please make sure you also have a shell script named ‘basic.sh’ and ‘efficient.sh’ with the commands required to run your program. For example, the contents of this file can be one of the following:

Sample code for memory and time calculation

Python

import sys

from resource import * import time

import psutil

def process_memory():

process = psutil.Process() memory_info =

process.memory_info()

memory_consumed = int(memory_info.rss/1024) return

memory_consumed

def time_wrapper(): start_time =

time.time() call_algorithm()

end_time = time.time()

time_taken = (end_time - start_time)*1000 return time_taken

Java

private static double getMemoryInKB() {

double total = Runtime.getRuntime().totalMemory(); return (total-Runtime.getRuntime().freeMemory())/10e3;

}

private static double getTimeInMilliseconds() { return

System.nanoTime()/10e6;

}

double beforeUsedMem=getMemoryInKB(); double startTime = getTimeInMilliseconds();

alignment = basicSolution(firstString, secondString, delta, alpha);

double afterUsedMem = getMemoryInKB(); double endTime = getTimeInMilliseconds();

double totalUsage = afterUsedMem-beforeUsedMem; double totalTime = endTime - startTime;

C/C++

#include <sys/resource.h> #include

<errno.h> #include <stdio.h>

extern int errno;

// getrusage() is available in linux. Your code will be evaluated in Linux OS.

long getTotalMemory() { struct rusage

usage;

int returnCode = getrusage(RUSAGE_SELF, &usage); if(returnCode == 0) { return usage.ru_maxrss;

} else {

//It should never occur. Check man getrusage for more info to

debug.

// printf("error %d", errno); return -1;

}

int main() {

struct timeval begin, end; gettimeofday(&begin, 0);

//write your solution here

//Please call getTotalMemory() only after calling your solution function. It calculates max memory used by the program.

double totalmemory = getTotalMemory(); gettimeofday(&end, 0); long seconds = end.tv_sec - begin.tv_sec;

long microseconds = end.tv_usec - begin.tv_usec; double totaltime = seconds*1000 + microseconds*1e-3; printf("%f\n", totaltime); printf("%f\n", totalmemory);

}

You will get a ZIP (99KB) file

CSCI-570-Final Project

You Might Also Like