Computing Edit Distance

Loading...

En provenance du cours de University of California San Diego

Algorithmic Toolbox

3700 notes

University of California San Diego

Algorithmic Toolbox

3700 notes

Cours 1 sur 6 dans Specialization Data Structures and Algorithms

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

À partir de la leçon

Dynamic Programming 1

In this final module of the course you will learn about the powerful algorithmic technique for solving many optimization problems called Dynamic Programming. It turned out that dynamic programming can solve many problems that evade all attempts to solve them using greedy or divide-and-conquer strategy. There are countless applications of dynamic programming in practice: from maximizing the advertisement revenue of a TV station, to search for similar Internet pages, to gene finding (the problem where biologists need to find the minimum number of mutations to transform one gene into another). You will learn how the same idea helps to automatically make spelling corrections and to show the differences between two versions of the same text.

The Alignment Game8:39

Computing Edit Distance6:37

Reconstructing an Optimal Alignment4:55

Rencontrer les enseignants

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Let's now see how dynamic programming algorithm solves the edit distance problem.

We start by considering two strings, A of length n and

B of length m and we will ask the question question what is an optimal alignment

of an i-prefix of A, which is the first i symbols of A, and

the j-prefix of B which are the first j symbols only.

The last column of an optimal alignment is either an insertion or

a deletion or a mismatch, or a match.

And please notice that if we remove the last column

from the optimal alignment of the strings, what is left

is an optimal alignment of the corresponding two prefixes.

And we can adjust the score of the optimal alignment for i prefix and

j prefix by adding plus 1 in the case of insertion, plus 1 in the case of deletion,

plus 1 in the case of mismatch and adding nothing in the case of match.

Let's denote D (i, j) to be the edit distance

between an i-prefix and a j-prefix.

And in this case,

this figure at the top of the slide illustrates the following recurrency.

D(i,j) equal to the minimum of the following four values:

D(i,j-1)+1, D(i-1,j)+1,

D(i-1,j-1)+1, in the case the last

two symbols in the i prefix of A and j prefix of B are different.

And D(i- 1, j- 1), if the last symbols in i and j prefix are the same.

Our goal now is to compute the edit distance D, i,

j between all i prefixes of string A and all j prefixes of string B.

In the case of string editing and distance we will construct eight by nine grid and

our goal is to compute all edit distances D(i, j)

corresponding to all nodes in this grid.

For example, for i and j equal to four and four.

How will we compute the corresponding distance D(i, j)?

Let's start by filling distances D(i, 0) in the first column of this matrix.

It is easy because indeed we are comparing an i-prefix

of string A against a 0-prefix of string D and

therefore this edit distance for i-prefix will be equal to i.

That's what's shown here, similarly we can easily fill the first row in this matrix.

And now let's try to compute what will be the distance D(1,1)

corresponding to comparison of string consisting of single symbol E,

with a string consisting of single symbol D,

there are three possible ways to arrive to the node (1, 1):

from the nodes (0, 0), (0, 1), and (1, 0).

Which one should be the way we will select to find the optimal edit distance.

According to the previous recurrency, we should select

the one of three directions that gives minimal value for

D(i, j), which is minimum of 2, 2, and 1 and

therefore we arrive to node (1, 1) by diagonal edge.

Let's keep this in memory that

the right direction to arrive at node (1, 1) was the diagonal direction.

We will now try to compute the edit distance for the next node in the matrix.

And in this case D(2,1) is equal to minimum D(2,0) + 1,

D(1,1) + 1 and D(1,0) of each tells us that's the optimal

way to arrive to this node would be again, by diagonal edge.

You continue further, once again compare three values and

it turn out that the best way to arrive to this node will be by vertical edge.

We'll continue further and we'll fill the whole second column in the matrix.

Now let's continue with the circle, what about this node?

For this node D(1,2) = minimum {D(1,1) + 1,

D (0,2) + 1, and D (0,1) + 1}.

And it is minimum of 2, 3, and 2.

In fact, there are two optimal ways to arrive to this node and

in this case we show both of them by diagonal edge

into this vertex and by horizontal edge of this vertex.

You'll continue further and slowly but surely we will fill the whole matrix.

The edit distance pseudocode implements the algorithm we just discussed.

It first fills in the first column and the first row of the dynamic programming

matrix and then it continues filling it up by computing the cost

of moving to vertex (i, j) using insertion, deletion,

or mismatch or match or in other words, exploring all possibility.

Moving to the vertex i, j using vertical edge, horizontal edge, and diagonal edge.

And then it finds out which of these possibilities

results in the minimum edit distance.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play