Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Computing Edit Distance

Loading...

Algorithmic Toolbox

Université de Californie à San Diego

4.7 (5,240 notes) | 160K étudiants inscrits

Cours 1 de 6 dans Structures de données et algorithmes Spécialisation

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). Do you have technical problems? Write to us: coursera@hse.ru

Visualiser le programme de cours

Compétences que vous apprendrez

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Avis

4.7 (5,240 notes)

5 stars
3,901 ratings
4 stars
1,063 ratings
3 stars
188 ratings
2 stars
38 ratings
1 star
50 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

AG

Aug 06, 2019

Thanks for the course, it was instructive! I like that some problems require implementing algorithms discussed in lectures, while others are quite challenging and are very satisfying to solve :)

À 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

Enseigné par

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcription

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.

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

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales