Feature #8: Similarity Measure Between DNA Samples

Description

The DNA of an alien species consists of a sequence of nucleotides, where each nucleotide is represented by a letter. We received two such DNA samples, and we need to measure the extent of similarity—also known as the edit distance—between them. The prevalent measure of similarity between these two samples is the minimum number of edits that are required to convert one DNA sample to the other.

Note: We are only permitted to insert, delete, or update a nucleotide in a DNA sample.

Given two DNA samples as strings, sample1 and sample2, we have to return the minimum number of operations that are required to convert sample1 to sample2.

The following examples may clarify this problem:

Solution

We’ll compare the sample1 string with the sample2 string, one character at a time. If the characters at the current position match, then no edit operation will be required.

On the other hand, if the characters at the current position in the two strings don’t match, we can perform one of the following three operations, whichever will result in the fewest edit operations:

• Insert a character to sample1 at the current position.
• Delete the character in sample1 at the current position.
• Replace the character in sample1 at the current position with the character at the current position in sample2.

The choice shown above can’t be made on the basis of local optimality. The actual cost of all of the choices given above must consider the edit cost for matching the rest of the characters in sample1 with the rest of the characters in sample2.

Let’s look at an example where we compare sample1 = abcdef with sample2 = azced. If we start the comparison on the first characters of the two strings, a, there will be a match. The second characters of the two strings are b and z, respectively. Over here, we can perform one of these three operations:

• If we insert z into sample1, then we must find the edit distance between the strings bcdef and ced.
• If we replace b with z, then we must find the edit distance between the strings cdef and ced.
• If we delete the character b, then we must find the edit distance between the strings cdef and zced.

Once we’ve considered all of these options, we must return the minimum number of edit operations that are required to convert sample1 to sample2. This will lead to a recursive problem formulation, which has several overlapping subproblems and optimal substructure. Therefore, we will solve this problem using dynamic programming.

We will use the concept of memoization, where we use an array to store the already solved subproblems. We have to match all the nucleotides of the two samples that are given. For this, we can use a 2D array to store the edit distances. Let’s call this array d, whose size is defined by n and m, the lengths of sample1 and sample2, respectively.

The value in d[i][j] will represent the edit distance between the substrings formed by the first i nucleotides of sample1 and the first j nucleotides of sample2. To compute the edit distance d[i][j], we can ...