Using The Visualization

Command Buttons

Run - Executes the similarity computation to completion of initialization, matrix fill, or traceback phase.

Step - Executes one step in similarity computation, e.g. calculate and display next V(i, j) value or traceback one step and display path in matrix and next character in alignment.

Reset - Clears current data model and allows user to execute with default parameters or select new model, input sequences, or scoring parameters.

Note: Once algorithm execution has begun, input values for model selection, alignment sequences S1 or S2, or scoring parameters can not be changed until Reset button is pressed.

MATRIX INITIALIZATION

The first stage in computing similarity alignment is to initialize the matrix. This is shown in one step whether  the Run or Step command buttons are pressed. The info Panel in the upper right displays the initialization formula by which matrix row and column 0 is calculated. The matrix is created of size M[m + 1, n +1] where n = length S1 and m = length S2, S1 is aligned horizontally and S2 vertically. In the active area the matrix will be displayed with the sequences to be aligned and the initialization values filled in. Following initialization pressing Run or Step command buttons begin the Matrix Fill stage when the values V(i, j) are computed.

MATRIX FILL

As you step or run through the matrix fill the score parameters, recurrence algorithms, and current scores are displayed in the info panel in the upper right. You will see something like:

Figure 1

The info panel displays the recurrence algorithm and the values used to calculate V(i, j).

Figure 2

Note the colors in the adjacent cells V(i -1, j), V(i - 1, j - 1), and V(i, j - 1) are color coded to match the corresponding recurrence component in the info panel as shown in fig.1. In the example above the value V(i, j) = 1  is the maximum value resulting from V(i - 1, j - 1) + s(i, j) = 2 + (-1) = 1. A traceback pointer is assigned from V(i, j) to V(i - 1, j - 1). In case of a tie traceback pointers are entered for all cells that equal the "winning" V(i, j).

TRACEBACK

Figure 3

The info panel for traceback shows the valid paths, that is the cells [(i-1, j) + w, (i-1,j-1) + s(i, j), (i, j-1) + w]  that equaled V(i, j) during matrix fill and also the path that is followed. In practice, an arbitrary but consistent choice is made as to which path to follow in the case of a tie. In the visualization program if values are tied the preferred path is V(i - 1, j), then V(i - 1, j - 1), then V(i, j - 1).

Figure 4

    The farthest upper left hand green bordered cell is the active traceback cell. In figure 4 we are aligning S₁[2] = A to S₂[2] = G. The matrix cell with the green value and regular black border indicated the traceback path,  (i -1, j - 1), that is being followed. So in figure 4 we are aligning the two characters resulting in a mismatch and no indel '_' is inserted.

The Gaps Model

The Gaps model is initialized the same as the End-space free or local alignment. Traceback begins at M(m, n). These choices are not dictated by model definition. To display the gaps algorithm the color coded current values in the matrix and info panel are not used. Traceback proceeds the same as the other models but the gapped alignment steps are shown in with magenta borders to highlight the difference.

The main difference is seen in computing V(i, j), matching sequence characters remains the same as other models but horizontal and vertical traceback (where the '_' gap spaces are inserted into an alignment) are computed by searching the current row and column from 0 to the current index for the maximum value + w.