appropriate meaning
approxriate meaning
,
p->x
approxiiate meaning
,
r->i
approximate meaning
,
i->m
approximate maeaning
,
insert a
approximate mataning
,
e->t
approximate matcning
,
a->c
approximate matching
,
n->hAllowable mutations:
(A variation on E.D. also allows transposition of two adjacent letters as a single op..)
© L . A l l i s o n |
Is useful in:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | - | A | C | G | T | A | C | G | T | A | C | G | T |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | - | . | . | . | . | . | . | . | . | . | . | . | . | . |
1 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
2 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
3 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
4 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
5 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
6 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
7 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
8 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
9 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
10 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
11 | G | . | . | . | . | . | . | . | . | . | . | . | . | . |
12 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | - | A | C | G | T | A | C | G | T | A | C | G | T |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
1 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
2 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
3 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
4 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
5 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
6 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
7 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
8 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
9 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
10 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
11 | G | . | . | . | . | . | . | . | . | . | . | . | . | . |
12 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | - | A | C | G | T | A | C | G | T | A | C | G | T |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
1 | A | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
2 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
3 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
4 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
5 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
6 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
7 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
8 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
9 | C | . | . | . | . | . | . | . | . | . | . | . | . | . |
10 | A | . | . | . | . | . | . | . | . | . | . | . | . | . |
11 | G | . | . | . | . | . | . | . | . | . | . | . | . | . |
12 | T | . | . | . | . | . | . | . | . | . | . | . | . | . |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | - | A | C | G | T | A | C | G | T | A | C | G | T |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
- | 0 | . | . | . | . | . | . | . | . | . | . | . | . | |
1 | A | . | 0 | . | . | . | . | . | . | . | . | . | . | . |
2 | C | . | . | 0 | 1 | . | . | . | . | . | . | . | . | . |
3 | T | . | . | . | . | 1 | . | . | . | . | . | . | . | . |
4 | A | . | . | . | . | . | 1 | . | . | . | . | . | . | . |
5 | C | . | . | . | . | . | . | 1 | . | . | . | . | . | . |
6 | C | . | . | . | . | . | . | . | 2 | . | . | . | . | . |
7 | T | . | . | . | . | . | . | . | . | 2 | . | . | . | . |
8 | A | . | . | . | . | . | . | . | . | . | 2 | . | . | . |
9 | C | . | . | . | . | . | . | . | . | . | . | 2 | . | . |
10 | A | . | . | . | . | . | . | . | . | . | . | 3 | . | . |
11 | G | . | . | . | . | . | . | . | . | . | . | . | 3 | . |
12 | T | . | . | . | . | . | . | . | . | . | . | . | . | 3 |
A C G T A C G T A C - G T | | | | | | | | | | A C - T A C C T A C A G T
|
. . . | |
---|---|---|
|
NW: D[i-1, j-1] | N: D[i, j-1] |
. . . |
W: D[i-1, j] |
|
f(NW, N, W) = min(NW + either 0 or 1, N+1, W+1)
D[0][0] = 0; // boundary condition for(j=1; j <= length of B; j++) D[0][j] = D[0][j-1] + 1; // boundary condition for(i=1; i <= length of A; i++) { D[i][0] = D[i-1][0] + 1; // boundary condition for(j=1; j <= length of B; j++) { var diag = D[i-1][j-1]; if( A[i] != B[j] ) diag++; //diag = 0 or 1 D[i][j] = min(diag, //match or change min( D[i-1][j] + 1, //deletion D[i][j-1] + 1)) //insertion }//for j }//for i
Other examples in, e.g. graph algorithms (later).