4.1. General Problem

So, we have seen earlier that if we just look blindly at every position and try to scan the word starting that position, we get something which is an order m, n square. Now, this solution when required as to fill in the table of size m times n, so obviously, every entry in the m times n table, we just have to look at a neighbors to fill it up.

This chunk introduces the initial problem we are discussing, which involves analyzing sequences of characters (or words). When we check every position without any optimization, it leads to a quadratic time complexity (O(m*n)), where m and n represent the lengths of two words being compared. To address this, we can use dynamic programming, where we fill a table of size m x n. Each entry in this table can derive its value using its neighboring entries, allowing us to fill the table efficiently.

Think of this as trying to find the longest path in a maze. If you just start exploring from each point randomly, it will take a long time to find the exit. However, if you keep track of where you’ve been and use that information to avoid unnecessary repeats, you can navigate much faster. Similarly, dynamic programming helps us avoid recalculating results we already know.

So, we can now look at a slightly more general problem than longest common subword which is more interesting computationally. So, what if we do not look for an exact match, but we allow ourselves to drop some letters. So, we have a subsequence not a subword, it allows us to drop some letters and now, if you want to know, after dropping some letters, what is the longest match we can find.

This chunk shifts our focus from finding the longest common subword (exact matches) to the longest common subsequence (LCS). In the LCS, we don’t need exact matches throughout the sequence; instead, we can drop characters from either word. This flexibility allows us to find longer matches between two sequences. The idea is to analyze how characters can be aligned even when some might be missing.

Imagine two friends are creating a scrapbook using different sets of magazine clippings. They don’t have to copy the layout exactly but want to create a similar theme. They drop some clippings as needed but ensure the overall message or theme remains coherent. This is akin to what we do when finding the longest common subsequence—matching the essence rather than exact details.

So, before we proceed it useful to look at why the longest common subsequence problem is interesting. One of the areas is in bioinformatics. Biologists are interested in identifying, how close two species are to each other in a genetic sense.

In this chunk, we explore the significance of the LCS problem in bioinformatics, particularly in assessing genetic similarities between species. DNA sequences are compared to understand evolutionary relationships. Finding the longest common subsequence allows scientists to identify genetic regions shared by species, giving insights into their connectivity.

Consider the way you trace your ancestry. By comparing your family tree with another person’s, you might find common ancestors. The longer the sequence of shared ancestors (the common subsequence), the closer your genetic relationship, similar to how LCS works with DNA.

So, let us try understanding inductive structure of this longest common subsequence problem directly. ... The first thing to note is that if I am looking for this longest common subword between these two, supposing I find that a0, in fact equal to b0. Now, I claim that, I should combine them in the solution, and then look for a solution in the rest.

Here, we delve into the induction principle behind solving the LCS. We start by considering the first character of each sequence. If they match, they are included in the LCS, and the problem is reduced to solving the LCS for the remaining parts of both sequences. If they do not match, we explore two subproblems: dropping the first character of the first sequence or dropping the first character of the second sequence and taking the maximum result from both approaches.

Imagine you are building a tower with blocks, and each block represents a character in a sequence. If the first block from each stack matches, you can stack them together, simplifying your tower. If they don’t match, you have to explore other options using different blocks to find the best possible tower you can build, reflecting the process of maximizing the LCS.

As usual let LCS(i, j) stand for the LCS of the problem starting at ai and bj. ... So if ai equals bj as we say, LCS(i, j) is 1 plus LCS(i + 1, j + 1).

This segment outlines a recursive formula for calculating the LCS. Using notations LCS(i, j), we can express the length of the LCS based on whether the characters at positions i and j match. If they do, the solution increases by one and we continue with the next characters. Otherwise, we analyze two scenarios (dropping one character from either sequence) and select the larger result.

Think of it as a scoring system in a game where you earn points for matching pairs. If you match two items, you score a point and can continue gameplay (recursive next step). If they don’t match, you need to choose which item to keep and score from. In this way, the recursive formula builds upon previously scored items to reach the final score (LCS length).

--