Division of the comparison problem along diagonals. (A) Sequence similarities are contained within diagonals of the comparison matrix. (B) A subset of these diagonals, separated by a fixed offset L, is simultaneously considered by each computing node and is referred to as “diagonal” (modulo L). (C) The diagonals are conceptually divided into segments of length L, delineated by broken horizontal lines. All k-mer matches in a specific sampled position (short, bold, line segments) along each diagonal segment are simultaneously detected in a single positional hash table. This is repeated for all sampled positions along diagonal segments. The k-mer matches that occur within the same diagonal segment are collated together and assigned a significance score.
