Question

Let us consider two sequences of characters \(S_{1}\) and \(S_{2}\), For example, we could have \(S_{1}=\) ASCMA \(^{*}\) MN and \(S_{2}=\) AXMC4ANR. Assuming that a subsequence of a sequence can be constructed by deleting any number of characters from any positions, use the dynamic programming approach to create an algorithm that finds the longest common subsequence of \(S_{1}\) and \(S_{2}\) This algorithm returns the maximum-length common subsequence of each sequence.

Short answer

The dynamic programming approach to solve this problem involves initializing a matrix, filling it according to whether characters at specific positions are equal or not, and then finding the longest common subsequence by tracing through the matrix.

Step-by-step solution

Initializing the DP Matrix

Initiate a 2D array (dp matrix) \(dp[i][j]\) of size \((n+1) \times (m+1)\), where \(n\) is the length of \(S_{1}\) and \(m\) is the length of \(S_{2}\). Each cell \(dp[i][j]\) represents the length of LCS of prefixes \(S_{1}[..i]\) and \(S_{2}[..j]\). As there is no common subsequence of two empty prefixes, we put \(dp[i][j] = 0\) where \(i = 0\) or \(j = 0\).

Filling Up the DP Matrix

Then for each character in the sequences \(S_{1}\) and \(S_{2}\) starting from index 1, fill the DP table with following conditions: If characters at \(S_{1}[i]\) and \(S_{2}[j]\) are same, then set \(dp[i][j] = dp[i-1][j-1] + 1\). If characters are not same, then set \(dp[i][j] = max(dp[i-1][j], dp[i][j-1])\). These two steps follow directly from the definition of LCS.

Finding the LCS

After filling of the dp matrix is complete, the entry \(dp[n][m]\) will be the length of the longest common subsequence. To find the subsequence itself, we start at \(dp[n][m]\) and move towards \(dp[0][0]\). If \(S_{1}[i]\) is equal to \(S_{2][j]\), then this character is part of the LCS. If not, then move to the direction of the maximum of \(dp[i-1][j]\) or \(dp[i][j-1]\).

Key concepts

Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is a classic example of dynamic programming, which focuses on finding the longest subsequence common to all sequences in a set of sequences. This problem is essential in fields like bioinformatics for DNA sequence analysis and text comparison algorithms. A subsequence is derived by deleting zero or more characters from the sequence without changing the order of remaining characters.
The core idea is to iteratively build up solutions to smaller subproblems to solve the overall problem. Given two sequences, the LCS problem involves constructing a two-dimensional (2D) array where each cell represents the length of the LCS of prefixes from both sequences. By carefully filling in this table using the rules of LCS, we can determine not only the length of the LCS but also reconstruct the sequence itself. This is done by backtracking through the 2D array once it's filled.

Sequence Alignment

Sequence alignment is a fundamental concept that involves arranging two sequences to highlight their similarities and differences. Aligning sequences is crucial in comparison tasks, such as comparing two DNA molecules or text files.
In the context of LCS, sequence alignment helps identify common subsequences by aligning sequences character by character. This helps in determining how elements in one sequence can pair up with elements in another, permitting conclusions about their relative similarity or difference.

• An identical alignment at a given position means the characters in both sequences match.
• Otherwise, the sequences might be shifted or include gaps, indicating differences or additional elements.

By using dynamic programming approaches, sequence alignment can be efficiently computed, even for large sequences, by evaluating partial solutions and systematically deriving the best global alignment.

2D Arrays

In dynamic programming, a 2D array is often employed to hold solutions to subproblems in a structured way. This is because many problems, like LCS, naturally extend the notion of tabulating or tabularizing intermediate results.
For the LCS problem, a 2D array, often referred to as the DP matrix, is set up to calculate and store the lengths of common subsequences for prefixes of both sequences. Each entry in this matrix represents a solution to a subproblem characterized by a pair of prefixes.

• The first row and the first column of the 2D array serve as boundary conditions initialized to zero, representing scenarios where one of the sequences has zero length.
• The rest of the matrix is filled based on comparisons of elements from each sequence, progressively building the solution using smaller subresults.

This structured approach helps to systematically and efficiently solve the LCS problem, providing both the length and the actual subsequence when the matrix is fully constructed.

Algorithm Design

Algorithm design for the LCS problem involves structuring a solution that efficiently calculates the longest common subsequence through a systematic process. It employs a step-by-step procedure, utilizing dynamic programming and making use of recurrence relations.
The algorithm initially fills a 2D array to document intermediate results of subsequences. It considers all pairs of prefixes of the sequences and uses a decision-making process to determine whether to include an element in the LCS or not.

• If the characters of both sequences match, the current cell's value is updated based on the diagonal cell value plus one.
• If they don't match, the cell is updated from the maximum of the adjacent upper cell or the left cell.

After filling the array, the algorithm traces back from the last entry to extract the actual sequence, piecing together the longest common subsequence. This meticulous process ensures an optimal solution, emphasizing efficient computational resource usage and clear operational steps. Each decision in designing this algorithm focuses on reducing computational redundancy, making it an exemplary case of dynamic programming.