Patent Document ID: 9740798
Application ID: 14213495

Base Claim:
1. A system for inexact search acceleration using reference data, the system coupled to a host computing system, the system comprising: one or more memory circuits storing a plurality of queries and a FM-index of the reference data, each query comprising a sequence of a plurality of characters; and one or more field programmable gate arrays coupled to the one or more memory circuits, the one or more field programmable gate arrays configured to select a query from the plurality of queries; select a first or next substring of the selected query, the first or next substring comprising a subsequence of characters of the selected query; read a first or next section of the FM-index from the one or more memory circuits and calculate a plurality of suffix array intervals for the first or next substring with a corresponding plurality of prepended characters in a first or next position; read a first or next character in the first or next position of the query and select a first or next suffix array interval of the plurality of suffix array intervals for the read first character; determine whether the first or next suffix array interval is valid and whether a beginning of the query has been reached; return a first search result when the first or next suffix array interval is valid and the beginning of the query has been reached; and return a second search result that no match of the query with the reference data was found when the first or next suffix array interval is not valid.

---

Claim 9:
9. The system of claim 1 , wherein the one or more field programmable gate arrays are further configured to convert the valid first or next suffix array interval to an alignment of the query with the reference data.