Dynamic programing matrix linearization schema.

<p>HIVE-hexagon implements a floating diagonal approach where the diagonal of the computation is maintained along the two sides of the current highest scoring path of the matrix. (<b>a</b>) We assume the optimal alignment will be along the diagonal. (<b>b</b>) Multiple insertions or deletions can result in the optimal path traversing outside the defined diagonal belt. (<b>c</b>) By defining a constant width to the diagonal and pre-computing cell scores line by line, the limits of the remaining diagonal matrix can float along with the likely optimal scoring path. (<b>d</b>) Furthermore, pre-computation of cells in the diagonal line by line allows the exclusion of regions which cannot possibly contain the highest scoring path. (<b>e</b>) The resulting minimized, dynamic diagonal matrix is linearized to further simplify the process and minimize the memory footprint required.