The possibility of ties when constructing the H matrix, and hence alternative equally valid alignments has already been discussed in Section 4.3. A more general problem is that there may be many alternative alignments with scores close to the optimum. Any one of the alternative alignments could be the `true' biologically meaningful alignment and so it is useful to be able to generate all alignments `close' to the optimal alignment.
Saqi and Sternberg (1991) determine alternative sub-optimal alignments by first calculating the H matrix and best path. They then identify the cells that contributed to the best path and reduce these by a preset value (normally 10% of the typical scoring matrix value). A new H matrix is then calculated and a new best path and alignment. This process is repeated iteratively to generate a series of global sub-optimal alignments. Zuker [Zuker, 1991] and Vingron and Argos [Vingron & Argos, 1990] describe methods to visualise alternative sub-optimal alignments on a dot-plot. A simple way to probe for stable parts of an alignment is to generate an alignment with standard parameters, then modify the gap penalties slightly, re-align and observe which regions of the alignment change (if any).