For the purpose of illustration, *K*_{max} is set to 2, and the weights *W*_{m}, *W*_{ms}, *W*_{in}, and *W*_{ib} are all set to 1. Alternative configurations for each site of the input fragment F (A) are stored in the matrix (B). For each *k*_{i} considered, 0, 1, and 2, a separate matrix is computed for *p* (C) and for *q* (D). Matrices for *k*_{i}>0 are initialized with basal values at each *i*≤*k*_{i}, shown in the grey cells. The remaining cells in the *p* matrices are filled out successively left to right and in the *q* matrices right to left. Each column has to be computed in all three matrices (one for each *k*_{i}) before proceeding to the next site. For *i*>*k*_{i}, computing each *p* and *q* requires first computing three *p*′ and *q*′ scores, correspondingly, one for each possible phase shift at the, respectively, preceding or following site. These calculations are omitted for space reasons, except for *p*(6, 2, 1), included as an example. The matrix of *ω*(*i*, *z*_{i}, *k*_{i}) is obtained by summation of *p* and *q* matrices; for each *i* the maximum values *ω* are highlighted (E). The configurations that received the maximum *ω*, and the corresponding *k*_{i} are selected (F) to form the aligned solution (G). The site 7 remains ambiguous because both corresponding alternative configurations have yielded equal *ω*. The post-processing algorithm determines that only one of these can be incorporated without mismatches (H). The optimal aligned solution is output in the customary form (I). Symbols and conventions are as in , except the bases having no homologs are shown on a black background.

## PubMed Commons