Minimum Edit Distance in Computational Linguistics

 
Minimum Edit
Distance
 
 
Definition of Minimum
Edit Distance
How similar are two strings?
 
Spell correction
The user typed “graffe”
Which is closest?
graf
graft
grail
giraffe
 
 
 
Computational Biology
Align two sequences of nucleotides
 
 
Resulting alignment:
 
Also for Machine Translation, Information Extraction, Speech Recognition
 
AGGCTATCACCTGACCTCCAGGCCGATGCCC
TAGCTATCACGACCGCGGTCGATTTGCCCGAC
 
-
AG
G
CTATCAC
CT
GACC
T
C
CA
GG
C
CGA
--
TGCCC
---
T
AG
-
CTATCAC
--
GACC
G
C
--
GG
T
CGA
TT
TGCCC
GAC
 
Edit Distance
 
In computational linguistics and computer science, 
edit distance
 is a
way of quantifying how dissimilar two strings (e.g., words) are to one
another by counting the 
minimum
 number of operations required to
transform one string into the other.
Levenshtein distance
 (LD) is a measure of the similarity between two
strings, which we will refer to as the source string (s) and the target
string (t). The 
distance
 is the number of deletions, insertions, or
substitutions required to transform s into t.
 
3
 
Edit Distance
 
 
The minimum edit distance between two strings
Is the minimum number of editing operations
Insertion
Deletion
Substitution
Needed to transform one into the other
 
Minimum Edit Distance
 
Two strings and their 
alignment
:
Minimum Edit Distance
 
If each operation has cost of 1
Distance between these is 5
If substitutions cost 2 (Levenshtein)
Distance between them is 8
Alignment in Computational Biology
 
Given a sequence of bases
 
An alignment:
 
 
Given two sequences, align each letter to a letter or gap
Especially, in 
bioinformatics
, it can be used to quantify the similarity of 
DNA
sequences, which can be viewed as strings of the letters A, C, G and T.
 
-
AG
G
CTATCAC
CT
GACC
T
C
CA
GG
C
CGA
--
TGCCC
---
T
AG
-
CTATCAC
--
GACC
G
C
--
GG
T
CGA
TT
TGCCC
GAC
AGGCTATCACCTGACCTCCAGGCCGATGCCC
TAGCTATCACGACCGCGGTCGATTTGCCCGAC
Other uses of Edit Distance in NLP
 
Evaluating Machine Translation and speech recognition
R 
Spokesman confirms    senior government adviser was shot
H 
Spokesman said    the senior            adviser was shot dead
              S      I              D                        I
Named Entity Extraction and Entity Coreference
IBM Inc
. announced today
IBM 
profits
Stanford President John Hennessy 
announced yesterday
for 
Stanford University President John Hennessy
 
How to find the Min Edit Distance?
 
Searching for a path (sequence of edits) from the start string to the
final string:
Initial state
: the word we’re transforming
Operators
: insert, delete, substitute
Goal state
:  the word we’re trying to get to
Path cost
: what we want to minimize: the number of edits
9
 
Minimum Edit as Search
 
But the space of all edit sequences is huge!
We can’t afford to navigate naïvely
Lots of distinct paths wind up at the same state.
We don’t have to keep track of all of them
Just the shortest path to each of those revisited states.
 
10
Defining Min Edit Distance
 
For two strings
X of length 
n
Y of length 
m
We define D(
i,j
)
the edit distance between X[1..
i
] and Y[1..
j
]
i.e., the first 
i
 characters of X and the first 
j
 characters of Y
The edit distance between X and Y is thus D(
n,m
)
 
Dynamic Programming for
Minimum Edit Distance
 
Dynamic programming
: A tabular computation of D(
n,m
)
Solving problems by combining solutions to subproblems.
Bottom-up
We compute D(i,j) for small 
i,j
And compute larger D(i,j) based on previously computed smaller values
i.e., compute D(
i,j
) for all 
i
 (0 < 
i
 < n)  and
 j 
(0 < j < m)
 
 
Defining Min Edit Distance (Levenshtein)
Initialization
D(i,0) = i
D(0,j) = j
Recurrence Relation
:
For each  i = 1…M
 
  For each  j = 1…N
                       
D(i-1,j) + 1
          D(i,j)= min  D(i,j-1) + 1
                       D(i-1,j-1) +   2; if X(i) ≠ Y(j)
                                      0; if X(i) = Y(j)
Termination
:
D(N,M) is distance
 
Computing alignments
 
Edit distance isn’t sufficient
We often need to 
align
 each character of the two strings to each other
We do this by keeping a “backtrace”
Every time we enter a cell, remember where we came from
When we reach the end,
Trace back the path from the Lower  right corner to read off the alignment
 
Adding Backtrace to Minimum Edit Distance
 
Base conditions:                                                        Termination:
D(i,0) = i         D(0,j) = j         D(N,M) is distance
Recurrence Relation
:
For each  i = 1…M
 
 For each  j = 1…N
                      
D(i-1,j) + 1
         D(i,j)= min  D(i,j-1) + 1
                      D(i-1,j-1) +  2; if X(i) ≠ Y(j)
                                    0; if X(i) = Y(j)
                     LEFT
         ptr(i,j)=   DOWN
                     DIAG
insertion
deletion
substitution
insertion
deletion
substitution
 
Weighted Edit Distance```
 
Why would we add weights to the computation?
Spell Correction: some letters are more likely to be mistyped than others
Biology: certain kinds of deletions or insertions are more likely than others
 
Confusion matrix for spelling errors
 
Weighted Min Edit Distance
Initialization:
D(0,0) = 0
D(i,0) = D(i-1,0) + del[x(i)];    1 < i ≤ N
D(0,j) = D(0,j-1) + ins[y(j)];    1 < j ≤ M
Recurrence Relation
:
             
D(i-1,j)   + del[x(i)]
D(i,j)= min  D(i,j-1)   + ins[y(j)]
              D(i-1,j-1) + sub[x(i),y(j)]
Termination
:
D(N,M) is distance
Sequence Alignment
 
-
AG
G
CTATCAC
CT
GACC
T
C
CA
GG
C
CGA
--
TGCCC
---
T
AG
-
CTATCAC
--
GACC
G
C
--
GG
T
CGA
TT
TGCCC
GAC
AGGCTATCACCTGACCTCCAGGCCGATGCCC
TAGCTATCACGACCGCGGTCGATTTGCCCGAC
 
Sequence Alignment
 
A sequence alignment is the way of arranging the
sequences of DNA, RNA and Proteins to identify the
regions of similarity that may be consequence of
functional, structural or evolutionary relationship
between the sequences.
 
Why sequence alignment?
 
Comparing genes or regions from different species
to find important regions
determine function
uncover evolutionary forces
Assembling fragments to sequence DNA
Compare individuals to looking for mutations
 
Alignments in two fields
 
In Natural Language Processing
We generally talk about 
distance 
(minimized)
And 
weights
In Computational Biology
We generally talk about 
similarity 
(maximized)
And 
scores
 
Global Alignment:
 
Global alignment
 is useful when you want to force two sequences to
align over their entire length.
Needs to find relationship between two sequences as a whole
The Needleman-Wunsch Algorithm
 
The Needleman-Wunsch Algorithm
Initialization:
D(i,0) = -i * d
D(0,j) = -j * d
Recurrence Relation
:
             
D(i-1,j)   - d
D(i,j)= max  D(i,j-1)   - d
             D(i-1,j-1) + s[x(i),y(j)]
Termination
:
D(N,M) is distance
 
The Needleman-Wunsch Algorithm
 
Initial Matrix of two strings
 
http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1
 
The Needleman-Wunsch Algorithm
 
Initialization:
 
http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1
 
The Needleman-Wunsch Algorithm
 
Alignment
Scores:
Match =+1
Mismatch=-1
(Subs)
Gap=-1
(Ins,
Del=indels)
 
http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1
 
The Needleman-Wunsch Algorithm
 
Possible Alignments with Trace backs
 
The Needleman-Wunsch Algorithm
 
      
T  C  G  C  A
 
T
C
C
A
 
TCGCA
TC-CA
 
Local Alignment
 
Local alignment
 methods find related regions 
within
 sequences - they
can consist of a 
subset
 of the characters within each sequence.
For example, 
positions 20-40
 of 
sequence A
 might be aligned with
positions 50-70
 of 
sequence B
.
This is a more flexible technique than 
global alignment
 and has the
advantage that 
related regions
 which appear in a different order in
the two proteins (which is known as 
domain shuffling
) can be
identified as being related.
This is 
not
 possible with 
global alignment
 methods.
 
The Smith-Waterman algorithm
 
Place each sequence along one axis
Place score 0 at the up-left corner
Fill in 1
st
 row & column with 
0s
Fill in the matrix with max value of 
4
 possible values:
0
Vertical move:  Score + gap penalty
Horizontal move:  Score + gap penalty
Diagonal move:  Score + match/mismatch score
The optimal alignment score is 
the max in the matrix
To reconstruct the optimal alignment, trace back where the MAX at each
step came from, stop when a 
zero
 is hit
The Smith-Waterman algorithm
 
Idea
: Ignore badly aligning regions
 
Modifications to Needleman-Wunsch:
 
Initialization
:
 
F(0, j) = 0
   
F(i, 0) = 0
    
                     
0
Iteration
:
F(i, j) = max    F(i – 1, j) – d
    
        F(i, j – 1) – d
    
        F(i – 1, j – 1) + s(x
i
, y
j
)
Slide from Serafim Batzoglou
 
Local alignment example
 
X = ATCAT
Y = ATTATC
 
Let:
 m = 1 
(1 point for match)
 d = 1 
(-1 point for del/ins/sub)
 
Local alignment example
 
X = ATCAT
Y = ATTATC
 
Local alignment example
 
X = 
ATCAT
Y = 
ATTAT
C
 
Local alignment example
 
X =    
ATC
AT
Y = 
ATT
ATC
 
 
 
Global vs. Local Alignments
 
Global alignment algorithms start at the
beginning of two sequences and add gaps to
each until the end of one is reached.
Local alignment algorithms finds the region
(or regions) of highest similarity between two
sequences and build the alignment outward
from there.
 
Global versus local alignments
 
Global alignment: align full length of both sequences.       (The
“Needleman-Wunsch” algorithm).
 
 
Local alignment: find best partial alignment of two sequences
(the “Smith-Waterman” algorithm).
 
Global alignment
 
Seq 1
 
Seq 2
 
Local alignment
Slide Note
Embed
Share

Edit distance, such as Levenshtein distance, quantifies the similarity between strings by counting operations needed for transformation. It finds applications in spell correction, DNA sequence alignment, machine translation, and speech recognition. The minimum edit distance measures the minimum number of editing operations like insertion, deletion, or substitution required to transform one string into another. Through alignment in computational biology, edit distance helps quantify similarity in DNA sequences.


Uploaded on Sep 09, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Minimum Edit Distance Definition of Minimum Edit Distance

  2. How similar are two strings? Spell correction The user typed graffe Which is closest? graf graft grail giraffe Computational Biology Align two sequences of nucleotides AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC Resulting alignment: -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC Also for Machine Translation, Information Extraction, Speech Recognition

  3. Edit Distance In computational linguistics and computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t. 3

  4. Edit Distance The minimum edit distance between two strings Is the minimum number of editing operations Insertion Deletion Substitution Needed to transform one into the other

  5. Minimum Edit Distance Two strings and their alignment:

  6. Minimum Edit Distance If each operation has cost of 1 Distance between these is 5 If substitutions cost 2 (Levenshtein) Distance between them is 8

  7. Alignment in Computational Biology Given a sequence of bases AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC An alignment: -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC Given two sequences, align each letter to a letter or gap Especially, in bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.

  8. Other uses of Edit Distance in NLP Evaluating Machine Translation and speech recognition R Spokesman confirms senior government adviser was shot H Spokesman said the senior adviser was shot dead S I D I Named Entity Extraction and Entity Coreference IBM Inc. announced today IBM profits Stanford President John Hennessy announced yesterday for Stanford University President John Hennessy

  9. How to find the Min Edit Distance? Searching for a path (sequence of edits) from the start string to the final string: Initial state: the word we re transforming Operators: insert, delete, substitute Goal state: the word we re trying to get to Path cost: what we want to minimize: the number of edits 9

  10. Minimum Edit as Search But the space of all edit sequences is huge! We can t afford to navigate na vely Lots of distinct paths wind up at the same state. We don t have to keep track of all of them Just the shortest path to each of those revisited states. 10

  11. Defining Min Edit Distance For two strings X of length n Y of length m We define D(i,j) the edit distance between X[1..i] and Y[1..j] i.e., the first i characters of X and the first j characters of Y The edit distance between X and Y is thus D(n,m)

  12. Dynamic Programming for Minimum Edit Distance Dynamic programming: A tabular computation of D(n,m) Solving problems by combining solutions to subproblems. Bottom-up We compute D(i,j) for small i,j And compute larger D(i,j) based on previously computed smaller values i.e., compute D(i,j) for all i (0 < i < n) and j (0 < j < m)

  13. Defining Min Edit Distance (Levenshtein) Initialization D(i,0) = i D(0,j) = j Recurrence Relation: For each i = 1 M For each j = 1 N D(i-1,j) + 1 D(i,j)= min D(i,j-1) + 1 D(i-1,j-1) + 2; if X(i) Y(j) 0; if X(i) = Y(j) Termination: D(N,M) is distance

  14. Computing alignments Edit distance isn t sufficient We often need to align each character of the two strings to each other We do this by keeping a backtrace Every time we enter a cell, remember where we came from When we reach the end, Trace back the path from the Lower right corner to read off the alignment

  15. Adding Backtrace to Minimum Edit Distance Base conditions: Termination: D(i,0) = i D(0,j) = j D(N,M) is distance Recurrence Relation: For each i = 1 M For each j = 1 N D(i-1,j) + 1 D(i,j)= min D(i,j-1) + 1 D(i-1,j-1) + 2; if X(i) Y(j) 0; if X(i) = Y(j) LEFT ptr(i,j)= DOWN DIAG substitution deletion insertion substitution insertion deletion

  16. Weighted Edit Distance``` Why would we add weights to the computation? Spell Correction: some letters are more likely to be mistyped than others Biology: certain kinds of deletions or insertions are more likely than others

  17. Confusion matrix for spelling errors

  18. Weighted Min Edit Distance Initialization: D(0,0) = 0 D(i,0) = D(i-1,0) + del[x(i)]; 1 < i N D(0,j) = D(0,j-1) + ins[y(j)]; 1 < j M Recurrence Relation: D(i-1,j) + del[x(i)] D(i,j)= min D(i,j-1) + ins[y(j)] D(i-1,j-1) + sub[x(i),y(j)] Termination: D(N,M) is distance

  19. Sequence Alignment AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC

  20. Sequence Alignment A sequence alignment is the way of arranging the sequences of DNA, RNA and Proteins to identify the regions of similarity that may be consequence of functional, structural or evolutionary relationship between the sequences.

  21. Why sequence alignment? Comparing genes or regions from different species to find important regions determine function uncover evolutionary forces Assembling fragments to sequence DNA Compare individuals to looking for mutations

  22. Alignments in two fields In Natural Language Processing We generally talk about distance (minimized) And weights In Computational Biology We generally talk about similarity (maximized) And scores

  23. Global Alignment: Global alignment is useful when you want to force two sequences to align over their entire length. Needs to find relationship between two sequences as a whole The Needleman-Wunsch Algorithm

  24. The Needleman-Wunsch Algorithm Initialization: D(i,0) = -i * d D(0,j) = -j * d Recurrence Relation: D(i-1,j) - d D(i,j)= max D(i,j-1) - d D(i-1,j-1) + s[x(i),y(j)] Termination: D(N,M) is distance

  25. The Needleman-Wunsch Algorithm Initial Matrix of two strings http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1

  26. The Needleman-Wunsch Algorithm Initialization: http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1

  27. The Needleman-Wunsch Algorithm Alignment Scores: Match =+1 Mismatch=-1 (Subs) Gap=-1 (Ins, Del=indels) http://vlab.amrita.edu/?sub=3&brch=274&sim=1431&cnt=1

  28. The Needleman-Wunsch Algorithm Possible Alignments with Trace backs

  29. The Needleman-Wunsch Algorithm T C G C A T TCGCA TC-CA C C A

  30. Local Alignment Local alignment methods find related regions within sequences - they can consist of a subset of the characters within each sequence. For example, positions 20-40 of sequence A might be aligned with positions 50-70 of sequence B. This is a more flexible technique than global alignment and has the advantage that related regions which appear in a different order in the two proteins (which is known as domain shuffling) can be identified as being related. This is not possible with global alignment methods.

  31. The Smith-Waterman algorithm Place each sequence along one axis Place score 0 at the up-left corner Fill in 1st row & column with 0s Fill in the matrix with max value of 4 possible values: 0 Vertical move: Score + gap penalty Horizontal move: Score + gap penalty Diagonal move: Score + match/mismatch score The optimal alignment score is the max in the matrix To reconstruct the optimal alignment, trace back where the MAX at each step came from, stop when a zero is hit

  32. The Smith-Waterman algorithm Idea: Ignore badly aligning regions Modifications to Needleman-Wunsch: Initialization: F(0, j) = 0 F(i, 0) = 0 Iteration:F(i, j) = max F(i 1, j) d F(i, j 1) d F(i 1, j 1) + s(xi, yj) 0 Slide from Serafim Batzoglou

  33. Local alignment example A T T A T C 0 0 0 0 0 0 0 A 0 T 0 C 0 A 0 T 0 X = ATCAT Y = ATTATC Let: m = 1 (1 point for match) d = 1 (-1 point for del/ins/sub)

  34. Local alignment example A T T A T C 0 0 0 0 0 0 0 A 0 1 0 0 1 0 0 T 0 0 2 1 0 2 0 C 0 0 1 1 0 1 3 A 0 1 0 0 2 1 2 T 0 0 2 0 1 3 2 X = ATCAT Y = ATTATC

  35. Local alignment example A T T A T C 0 0 0 0 0 0 0 A 0 1 0 0 1 0 0 T 0 0 2 1 0 2 0 C 0 0 1 1 0 1 3 A 0 1 0 0 2 1 2 T 0 0 2 0 1 3 2 X = ATCAT Y = ATTATC

  36. Local alignment example A T T A T C 0 0 0 0 0 0 0 A 0 1 0 0 1 0 0 T 0 0 2 1 0 2 0 C 0 0 1 1 0 1 3 A 0 1 0 0 2 1 2 T 0 0 2 0 1 3 2 X = ATCAT Y = ATTATC

  37. Global vs. Local Alignments Global alignment algorithms start at the beginning of two sequences and add gaps to each until the end of one is reached. Local alignment algorithms finds the region (or regions) of highest similarity between two sequences and build the alignment outward from there.

  38. Global versus local alignments Global alignment: align full length of both sequences. (The Needleman-Wunsch algorithm). Global alignment Local alignment: find best partial alignment of two sequences (the Smith-Waterman algorithm). Seq 1 Local alignment Seq 2

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#