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.
展开▼
