Method and apparatus for performing similarity searching

Abstract

Apparatuses and methods are disclosed for comparing a first biosequence string with a second biosequence string to assess similarity between those biosequence strings. For example, a field programmable gate array (FPGA) can be used to (1) detect substrings of the second biosequence string that are matches to substrings of the first biosequence string, and (2) map the detected substrings of the second biosequence string to corresponding positions in the first biosequence string where the detected substrings are located based on a data structure that links substrings of the first biosequence string to positions in the first biosequence string where the substrings of the first biosequence string are located. These operations can be used to seed an alignment between the first and second biosequence strings that permits comparisons to be performed over longer substrings of the first and second biosequence strings so that similarities between those longer substrings can be quantified.