Inexact search acceleration

A system for inexact search acceleration using a reference sequence for proteomic analysis, the system coupled to a host computing system, the system comprising:

• one or more memory circuits configured to store a plurality of queries and an FM-index of the reference sequence, 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 or next 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 sequence was found when the first or next suffix array interval is not valid.

A system for inexact search acceleration using a reference sequence for proteomic analysis, the reference sequence comprising a reference protein sequence, the system comprising:

• one or more memory circuits configured to store a plurality of queries and an FM-index of the reference sequence, 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 or next 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, the first search result comprising an alignment of the query with the reference sequence or comprising the valid first or next suffix array interval;
• and return a second search result that no match of the query with the reference sequence was found when the first or next suffix array interval is not valid.