CS 320 - Dynamic Programming Assignment: Algorithms and Solutions

This document presents a solution to a dynamic programming assignment, focusing on two key problems: sequence alignment and finding the longest path in a matrix. The solution addresses both local and global sequence alignment using the longest common subsequence (LCS) and longest increasing subsequence (LIS) concepts. It includes an alignment matrix to demonstrate the solution. The second part of the solution involves a C++ code implementation to find the longest path in a 2D matrix, utilizing dynamic programming techniques with memoization to optimize the search. The code includes functions to find the longest path from a cell and the overall longest path in the matrix. The document also references two relevant research papers on sequence alignment and visualization, namely VISTA and the Clustal series program, respectively, to provide context and further reading on the topics.

Dynamic Programming 1
Q1.Alignment Matrix
Alignment for local and global alignments
 S1 = GCCCTAGCG
 S1'' = GCG
 S2'' = GCG
 S2 = GCGCAATG
(G,C,C,C,T,A,G,C,G) and (G,C,G,C,A,A,T,G) is used in the solution due to Longest Common Subsequence
(LCS) and LIS.
Local alignment is S1'' and S2''
Global alignment is S1 and S2
Q.2
#include<bits/stdc++.h>
#define n 3
using namespace std;
// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
// Base case
if (i<0 || i>=n || j<0 || j>=n)
return 0;
// If this subproblem is already solved
if (dp[i][j] != -1)
return dp[i][j];

Dynamic Programming 2
// Since all numbers are unique and in range from 1 to n*n,
// there is atmost one possible direction from any cell
if (j<n-1 && ((mat[i][j] +1) == mat[i][j+1]))
return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);
if (j>0 && (mat[i][j] +1 == mat[i][j-1]))
return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);
if (i>0 && (mat[i][j] +1 == mat[i-1][j]))
return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);
if (i<n-1 && (mat[i][j] +1 == mat[i+1][j]))
return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);
// If none of the adjacent fours is one greater
return dp[i][j] = 1;
}
// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
int result = 1; // Initialize result
// Create a lookup table and fill all entries in it as -1
int dp[n][n];
memset(dp, -1, sizeof dp);
// Compute longest path beginning from all cells
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (dp[i][j] == -1)
findLongestFromACell(i, j, mat, dp);
// Update result if needed
result = max(result, dp[i][j]);
}
}
return result;
// Driver program
int main()
{
int mat[n][n] = {{2, 1, 1, 3},
{3, 2, 3, 6},
{4, 2, 4, 5}
{{5, 1, 5, 4}};
cout << "Length of the longest path is "
<< finLongestOverAll(mat);
return 0;
References

Dynamic Programming 2
Mayor, Chris, “VISTA: visualizing global DNA sequence alignment of arbitrary
length. Bioinformatics 16.11 (2000)
Chenna, Ramu. Multiple sequence alignment with the Clustal series
Program.”Nucleic acids research 31.13(2003)