5.5. Applications in Genetics

So, this distance is also called the Levenshtein distance, because it was first proposed by the Soviet, now Russian scientist called Vladimir Levenshtein and this like the longest common subsequence problem, it is extremely useful in practice.

The Levenshtein distance is a way to quantify how different two strings (such as words or sequences) are. It counts the minimum number of single-character edits (insertions, deletions, substitutions) required to change one word into another. This concept, introduced by Vladimir Levenshtein, is particularly useful in various applications, including spell checking and DNA sequence analysis.

Think of the process of correcting a word in a text. If you mistyped 'speling' instead of 'spelling', the spell checker uses edit distance to determine how many changes it needs to make (in this case, substituting the 'e' for 'a' and adding a 'l') to give you the correct word.

So, if you want to compare the genetic information in two different species, then it is natural to compare them in terms of the content of the DNA... how easy or difficult it is to transform one piece of DNA to another and depending on that we can tell whether two species are close to each other or not.

In genetics, the edit distance helps researchers compare the DNA sequences of different species. By calculating how many edits (like substitutions, insertions, or deletions) are needed to change one DNA sequence into another, scientists can infer how closely related two species are. A smaller edit distance generally indicates closer genetic relationships.

Imagine two friends who often use similar phrases in their conversations. If you wanted to compare their speech patterns and noticed how many different words or phrases they swapped to communicate the same idea, you could assess how similar they are in communication styles. Similarly, the edit distance compares genetic sequences in a way that helps define relationships among species.

The first thing is to suggest spelling corrections...gives a meaningful query based on what was mistyped.

One practical application of edit distance is in spell checkers and search engines. When someone types a word incorrectly, these systems use edit distance to find the closest correct word from a dictionary. Likewise, in search engines like Google, if a user mistypes a search query, the system may suggest corrections based on the edit distance to ensure that results are relevant.

Consider typing in a search bar, 'restraunt' instead of 'restaurant'. Google's algorithm will identify that your typed word is similar to 'restaurant' using edit distance principles, thus suggesting the correct term as a convenient option.

If the edit distance is suppose to be the minimum number of changes, it cannot be more than 48, because they already shown that it is possible to do it in 48 characters...

The edit distance calculation establishes a limit on the number of modifications needed to convert one string into another. For example, if transitioning from 'version1' to 'version2' involves 28 characters being inserted, 18 being deleted, and 2 substituted, the maximum edit distance would be 48. This insight allows for further optimization, as the real edit distance could be even smaller than this maximum.

Imagine you are moving to a new house and you need to count how many boxes you need to pack and how many items need to be discarded or replaced. By carefully evaluating what needs to be changed, you can avoid needless effort and streamline your moving process, just like edit distance helps in optimizing string transformations.

--