Q2) Use the dynamic programming approach to: (i) Find the longest common subsequ
ID: 3606243 • Letter: Q
Question
Q2) Use the dynamic programming approach to:
(i) Find the longest common subsequence (LCS) of the two sequences (row sequence and column sequence) assigned to you. Show the table for the length of the LCS of any two subsequences of the given sequences (as discussed in the slides), identify the length of the LCS as well as deduce the alignment (including the gap), as discussed in the slides.
(ii) Use the table determined for (i) to find the length of the LCS of the subsequences comprising the first five characters of the row and column sequences as well as deduce the alignment (including the gap).
Row Sequence Column Sequence GCTATTAT ATAGAAATC
Explanation / Answer
import java.util.*;
// class LongestCommonSubsequence definition
class LongestCommonSubsequence
{
// Returns length of longest common subsequence for firstString[0 to fLen - 1], secondString[0 to sLen - 1]
static void longestCommonSubsequence(String firstString, String secondString, int fLen, int sLen)
{
// Creates an two 2D integer array having
// firstString length + 1 as number of rows
// secondString length + 1 as number of columns
int[][] L = new int[fLen + 1][sLen + 1];
// The L[r][c] contains length of longest common subsequence of
// fistString[0 to r - 1] and secondString[0 to c - 1]
// Loops till firstString length
for (int r = 0; r <= fLen; r++)
{
// Loops till secondString length
for (int c = 0; c <= sLen; c++)
{
if (r == 0 || c == 0)
L[r][c] = 0;
else if (firstString.charAt(r - 1) == secondString.charAt(c - 1))
L[r][c] = L[r - 1][c - 1] + 1;
else
L[r][c] = Math.max(L[r - 1][c], L[r][c - 1]);
}// End of for inner loop
}// End of for outer loop
// Extracts the number stored at fLen and sLen position and stored it in index
int index = L[fLen][sLen];
// Creates a duplicate copy of the index
int temp = index;
// Create a character array to store the longest common subsequence string
char[] lcs = new char[index+1];
// Set the terminating character at the index position of the array
lcs[index] = '';
// Start from the right-most-bottom-most corner and one by one store characters in lcs[]
int r = fLen, c = sLen;
// Loops till r and c both are greater than zero
while (r > 0 && c > 0)
{
// If current character in firstString and secondString are same,
// Then current character is part of longest common subsequence
if (firstString.charAt(r - 1) == secondString.charAt(c - 1))
{
// Put current character in result array lcs
lcs[index - 1] = firstString.charAt(r - 1);
// Reduce values of r, c and index
r--;
c--;
index--;
}// End of if
// Otherwise they are not same
// Then find the larger of two and go in the direction of larger value
else if (L[r - 1][c] > L[r][c - 1])
r--;
else
c--;
}// End of while
// Print the longest common subsequence lcs array
System.out.print("LCS of " + firstString + " and " + secondString + " is: ");
// Loops till end of lcs
for(int p = 0; p < temp; p++)
System.out.print(lcs[p]);
}// End of method
// main method definition
public static void main (String[] args)
{
// Creates a Scanner class object
Scanner sc = new Scanner(System.in);
// Declares two strings to store data
String firstString;
String secondString;
// Accepts data
System.out.println("Enter Row Sequence string: ");
firstString = sc.next();
System.out.println("Enter Column Sequence string: ");
secondString = sc.next();
// Stores the length of each string
int fLen = firstString.length();
int sLen = secondString.length();
// Calls the method to display longest common subsequence
longestCommonSubsequence(firstString, secondString, fLen, sLen);
}// End of main method
}// End of class
Sample Run:
Enter Row Sequence string:
GCTATTAT
Enter Column Sequence string:
ATAGAAATC
LCS of GCTATTAT and ATAGAAATC is: ATAT
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.