Given two sequences V and W, the alignment graph is a directed acylic graph G on
(n + 1) × (m + 1) nodes, each labeled with a pair of positions (i, j) ((0 ≤ i ≤ m,
0 ≤ j ≤ n)), with three types of weighted edges: horizontal edges from (i, j) to (i +
1, j) with weight δ(v(i + 1), −), vertical edges from (i, j) to (i, j + 1) with weight
δ(−, w(j + 1)), and diagonal edges from (i, j) to (i + 1, j + 1) with weight δ(v(i + 1),
w(j + 1)), where δ(v i , −) and δ(−, w j ) represent the penalty score for indels, and