a
c
t
a a c g a c g a0
1
1 2 3 4 5 6 7 8
2
3
4
a
g
a
g
8
5
6
7
0 1 2 3 4 5 6 87
c
- a c g t
- -1 -1 -1 -1
a -1 1 -1 -1 -1
c -1 -1 1 -1 -1
g -1 -1 -1 1 -1
t -1 -1 -1 -1 1
g
a
ga c
2 1 33
2
1
3 3 41
3
2
G
a a c g a c g
c
t
a
c
3/4
a
c
g
a c
g
g
Trie for A Trie for B
0
13
5
0
3
2
g
a
g
a
a
5/4
2
t
4
g
5/2
3/2
left
prefix (5/2)
diagonal
prefix (3,2)
top
prefix (3,4)
Graph G
for Block (5,4)
LZ78-Partitioned
Alignment Graph
g
a
ga c
a
ga c
g
a
a c
a
a c
1 2 3 40
1
2
3
4
5
1
4
0 1 2 3 4
DIST(5,4)
0
1
2
3
4
5
-3
-1
1
0
0
-2
-3
-1
-2
-1
-1
-3
-2
-1
0
-2
-2
0
-2
-2
-1
-1
0
-2
0
-1
-2
a
g
a
c
g
g
Trie for A Trie for B
0
13
0
31
2
4
2
t
4
g
Block Table
5
c
I
O
I
S
C
E
I
O
i
jDIST[i,j ]
A
B C