4.6. Tracing Back the LCS

So, we can now look at a slightly more general problem than longest common subword in one which is more interesting computationally. So, what if we do not look for an exact match, but we allow a self should drop some letters. So, we have a subsequence not a subword, it is 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 introduces the concept of the Longest Common Subsequence (LCS), which is a problem that extends the idea of finding the longest common subword. Unlike subwords, which require exact matches, subsequences allow for the dropping of letters. This means we can find matches even when some characters are not present. Essentially, the LCS problem asks: Given two strings, what is the longest sequence that appears in both, allowing for some characters to be omitted.

Think of it like trying to find common themes in two different books. You don't need the exact sentences to match, but if certain phrases or ideas are similar, you can note them as part of a 'common storyline.' This flexibility reflects how subsequences work - you can 'drop' some words but still recognize a shared theme.

So, before we proceed it useful to look at why the longest common subsequence problem is interesting. So, one of the area is an bio informatics. So, biologist are interested in identifying, how close two species are each other in the genetic sense.

This chunk highlights the importance of the LCS problem in various fields, particularly in bioinformatics. In biology, the strings being compared are typically sequences of DNA, which consist of a long string over an alphabet of size four (A, T, G, C). By finding the LCS between two DNA sequences, researchers can infer how closely related two species are based on their genetic similarities, even when certain genes are missing or are located in different positions.

Imagine comparing two different species' DNA as reading two recipes for a dish. Both recipes may use similar ingredients (representing the common sequence), but some ingredients might be missing or reorganized. By understanding which ingredients are common, we can determine how closely related the dishes (or species) are, similar to finding the LCS in DNA.

So, the first thing to note is that if I am looking for this longest common subword between these two, supposing I find that a 0, in fact equal to b 0. Now, I claim that, I should combine them in the solution, and then look for a solution in the rest.

In this portion, the discussion revolves around the inductive structure of finding the LCS. It posits that if the first characters of the two sequences match (denoted as a[0] and b[0]), then those characters should be included in the LCS and the search for other matches should continue from the next characters. This recursive approach reinforces the idea that building upon the known matches helps in effectively solving larger subproblems.

Consider a jigsaw puzzle where you manage to fit the first piece perfectly (a[0] and b[0] matching). Once these pieces are combined, you can focus on fitting the next pieces (the remaining characters). This focused approach makes solving the rest of the puzzle simpler, just like checking the rest of the characters in LCS.

Now, if it is not equal, then one is not sure what you do, it is not s sound idea a to drop both. So, for instant supposing I have something like straw and astray, then just because the S does not match the a, does not mean that I should in both of them, I should keep that S alive to match with next S.

The text explains the case when the characters being compared do not match. If a[0] does not equal b[0], you cannot simply ignore both characters. Instead, the algorithm needs to explore the possibility of matching one character while retaining the other for potential matches later in the sequences. This creates multiple subproblems to evaluate which character to keep, ensuring the longest valid match is found.

Imagine you're assembling a team and have two candidates. Just like two letters in our sequences, not every feature of each candidate may match completely. You might want to keep one candidate for their unique skills while checking if the other can fill a role later on, emphasizing the importance of maintaining options while searching for the best combination.

So, as usual let LCS i comma j, stand for the LCS of the problem starting at a i and b j.

This chunk introduces the notation used for the LCS function. It defines LCS(i, j) as the longest common subsequence considering subsequences starting at indices i and j in sequences a and b respectively. The rules for computing the values are established, showing a recursive formula to derive lengths based on character comparisons and previous LCS results.

Think of it as tracking delivery of packages. Each index represents a point in the delivery chain; LCS(i, j) helps determine how many packages can be successfully delivered together when starting from points i and j. If they match, you add to the tally; if not, you check both delivery routes to maximize efficiency.

So, this is similar to LCW, we basically fill out in m, n size table each entry in the table is easy to compute takes only constant among look at the three neighbors.

This section describes how the Longest Common Subsequence (LCS) table is systematically filled out, similar to the process used for the Longest Common Word (LCW). Each entry in the m by n table can be computed by examining a constant number of neighboring entries, using the previously established rules for matching and dropping characters.

Picture laying out a grid for a game like 'Connect Four.' Each spot on the grid can hold a piece based on your move rules. Similarly, each entry in the LCS table derives its value based on previous choices, allowing you to build steadily towards a winning combination (the longest common subsequence).

And now as before you can trace back the path, why was each value filled, was it filled, because it to 1 plus i plus 1, j plus 1 or it goes to fill, because max with other two networks.

Finally, this block discusses the traceback process used after computing the LCS values to determine the actual subsequence itself. By following the filled values in the table, one can retrace the steps taken to form the longest subsequence, identifying which characters were included during the process.

Imagine you've just completed a riddle or puzzle. Retracing your thought process allows you to see how you arrived at the final answer. Likewise, when we trace back from the completed LCS table, we unveil the steps taken to derive the longest common subsequence from our original sequences.

--