A digital hardware system slides a sequence to be searched, such as a genome,
past
a query sequence, such as a DNA fragment, via shift registers. In parallel, multiple
alignments between search and query sequences are compared. As each alignment consists
of many elements (characters), the parallel matching process is highly accelerated
over sequential element-by-element comparison. Individual element comparisons are
made using equivalence operators, such as XNOR logic gates. The results of individual
element comparisons are then consolidated into a single signal: "hit" or "miss",
indicating whether all the elements for the particular alignment under test matched
or not. After comparison, the search sequence is shifted by a number of elements
equal to the number of parallel alignments compared, and the process repeats. An
additional shifting prefetch buffer increases memory efficiency by alleviating
the need to fetch data every cycle.