Description
2 Dynamic Programming
Solve the the following Dynamic Programming problem with optimization using C++ programming language.
1. The similarity between two strings where similarity of two strings X and Y is defined
as M which is gap penalty or mismatch cost for pair of characters at same index in the
two strings. Gap penalty and Mismatch cost is as defined in the book by Kleinberg and
Tardos section 6.6.
2. You need to align two input DNA Sequences such that this cost of M for these two
sequences is minimum.
3. Basic correct implementation of the algorithm – (Marks-10)
4. Optimization in Linear Space via Divide and Conquer (Marks-20)
Above marks will be provided only if below mentioned files are present.
You can implement these in two cpp files, one for first part and other for second part.
For the evaluation of the above files, each file should take two DNA strings as input and
output the optimal alignment of the two strings and its cost as per the gap and mismatch cost.
Output Format –
Optimal Alignment of String 1
Optimal Alignment of String 2
Cost =
Use − to represent a gap in string alignment.
See sample I/O for more understanding
Compile the files to take an argument from the command line as 1 or 2.
1. If argument is 1 – gap penalty = 6, mismatch penalty = 4
2. If argument is 2 – gap penalty = 4, mismatch penalty = 6
Note: We will run the code in given format –
./part1 1
./part1 2
./part2 1
./part2 2
Sample Input Output:
argument 1 –
Input –
ATAT
GCAT
Output –
ATAT
GCAT
Cost = 8
argument 2 –
Input –
ATAT
TATA
Output –
-ATAT
TATACost = 8
IMPORTANT:
Do not hard code anything for any of the part. The argument change should only change the
penalty values and should have no other change in the code.
BONUS:
2
Take input an argument three and have different penalty values for A-G and T-C mismatch from
the usual mismatch penalty.
3