Alignment Algorithm Demo
Scroll down for the applet
This applet gives a demonstration of several different alignment algorithms.
Some algorithms determine an optimal alignment, some only
the edit cost. The values in each cell are only
displayed if there is room.
The green cells indicate a cell which has been computed by
the algorithm. A blue cell indicates that this cell is currently being
Note that some of these algorithms, such as Ukkonen's Algorithm, do
not actually compute using this 2d matrix. In these cases, the
animated matrix shows cells that are implicitly calculated by the algorithm.
This is the simple DPA for point mutation costs,
match=0, mismatch=1, insert/delete=1.
Each cell of the matrix, D[i][j], contains the edit cost for the sequences
s1[1..i] and s2[1..j]. An optimal alignment is drawn through the matrix
This is a modified version of the standard DPA which computes a smaller region
of the D matrix (runs in O(nd) time).
Ukkonen's algorithm runs in O(d*d + n) time. This algorithm does not use the
D matrix like the other DPA algorithms. However, Ukkonen's algorithm is shown
here operating of the standard matrix to give an idea as to which cells of the
DPA matrix it computes. Blue cells indicate a cell currently being computed.
Green cells indicate cells that have already been computed.
Hirschberg presented a modification of the DPA that allows an optimal
alignment to be found in O(n) space. Green cells are cells that have been
computed and are currently stored. Yellow cells indicate cells that are known
to lie on the optimal alignment.
This algorithm is the O(n2
) DPA for linear gap
costs, with gaps costed as a+b*k where a=3, b=1, matches=0,
This is Ukkonen's algorithm for linear gap costs (same costs
as for the Linear DPA case).