Method and apparatus for performing similarity searching

US10957423B2 · kind B2 · utility

Assignee

• Washington University · US

Inventors

• Jeremy Daniel Buhler · Clayton, US
• Roger D. Chamberlain · Chesterfield, US
• Mark Allen Franklin · Chesterfield, US
• Kwame Gyang · Chesterfield, US
• Arpith Chacko Jacob · Chesterfield, US
• Praveen Krishnamurthy · Chesterfield, US
• Joseph M. Lancaster · Chesterfield, US

Key dates

• Filing date: Feb 28, 2020
• Grant date: Mar 23, 2021
• Expiry date: Feb 28, 2040

Classification

• Technology area (CPC G): Physics
• CPC primary: G16B50/00
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

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.