Method of aligning strings of characters representing genomic data and related hardware device

A method of aligning a first string (read) of characters representing genomic data to a second string (contig) of characters representing genomic data, using at least a pipelined Finite State Machine and a storage memory, the method comprising the steps of:

• providing a FPGA or an ASIC configured to implement said Finite State Machine, wherein said storage memory is an internal memory of said FPGA or ASIC;
• loading into said storage memory said first string (read) of characters representing genomic data;
• loading into said storage memory said second string (contig) of characters representing genomic data;
• carrying out cyclically the following steps using said Finite State Machine until all characters of said first string (read) have been compared:
• first state:
• selecting a first block of consecutive characters of said first string (read) of characters and a second block of consecutive characters of said second string (contig) of characters to be compared, said first block and said second block comprising an equal number of characters, a start position of said first block being identified by a first index and a start position of said second block being identified by a second index,
• second state:
• determining new values for said second index and for said first index to be used at a successive cycle assuming that the first block of consecutive characters of said first string (read) and the second block of consecutive characters of said second string (contig) do not align,
• third state:
• comparing in parallel characters of said first block, identified by said first index identified in first state, of consecutive characters of the first string (read) with corresponding characters of said second block, identified by said second index identified in first state, of consecutive characters of the second string (contig),
• fourth state:
• evaluating the result of the comparison performed at third state so that:
• 1) if the first block, identified by said first index identified in first state, of consecutive characters of the first string (read) and the second block, identified by said second index identified in first state, of consecutive characters of the second string (contig) do not align, returning at first state using the index identified at second state;
• 2) If the first block, identified by said first index identified in first state, of consecutive characters of the first string (read) and the second block, identified by said second index identified in first state, of consecutive characters of the second string (contig) align, the indexes of said first block and said second block identified at second state are discarded and new indexes are calculated, then returning at first state using the indexes calculated during the fourth state;
• 3) The comparison ends when either all blocks of the first string (read) successfully aligned to an equal number of blocks of the second string (contig), storing the results into said storage memory, or when there is no match of all blocks of the first string (read) with an any possible sequence of equivalent number of contiguous blocks of second string (contig), storing the results into said storage memory.