Inexact Search Acceleration

A system for inexact search acceleration using reference data, 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;
• returning a first search result when the first or next suffix array interval is valid and the beginning of the query has been reached;
• and returning 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.

A method for inexact search acceleration using reference data, the method comprising:

• using a field programmable gate array, selecting a query from a plurality of queries, each query comprising a sequence of a plurality of characters;
• using the field programmable gate array, selecting a first or next substring of the selected query, the first or next substring comprising a subsequence of characters of the selected query;
• using the field programmable gate array, reading a first or next section of an FM-index of the reference data from a memory circuit and calculating 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;
• using the field programmable gate array, reading a first or next character in the first or next position of the query and selecting a first or next suffix array interval of the plurality of suffix array intervals for the read first character;
• using the field programmable gate array, determining whether the first or next suffix array interval is valid and whether a beginning of the query has been reached;
• using the field programmable gate array, when the first or next suffix array interval is valid and the beginning of the query has not been reached, reading a next section of the FM-index from the memory circuit and calculating a next plurality of suffix array intervals for a next substring with a corresponding plurality of prepended characters in a next position;
• reading a next character in the next position of the query and selecting a next suffix array interval of the next plurality of suffix array intervals for the read next character;
• and determining whether the next suffix array interval is valid and whether a beginning of the query has been reached;
• using the field programmable gate array, when the first or next suffix array interval is valid and the beginning of the query has been reached, returning a first search result with an alignment of the query with the reference data;
• and
• using the field programmable gate array, when the first or next suffix array interval is not valid, returning a second search result with no alignment of the query with the reference data.