Genome graph analysis method, device and medium based on in-memory computing

A genome graph analysis method based on in-memory computing, comprising:

• step (1) construction:
• combining a linear reference genome with genetic variation to construct a genome graph;
• step (2) indexing:
• generating indexes for a plurality of vertices of the genome graph, and constructing an index table according to the generated indexes;
• step (3) seeding:
• dividing a read length into a plurality of substrings with a length of k-mer, querying the index table to obtain a seed position, generating a reference subgraph according to the seed position, and identifying a candidate mapping position according to the reference subgraph to filter a candidate mapping area;
• sub-step (3.1) receiving, by the read length traverser, an input read length from a host, wherein a seed processing unit comprises a read length traverser and a seed finder;
• sub-step (3.2) traversing, by the read length traverser, the input read length in order to obtain a plurality of minimizers, and scoring the plurality of minimizers according to a scoring mechanism to obtain a plurality of optimized minimizers;
• sub-step (3.3) storing the acquired minimizers in a minimizer cache region and counting the minimizers;
• sub-step (3.4) filtering, by the read length traverser, minimizers smaller than a first preset threshold and minimizers larger than a second preset threshold after traversing all characters in the read length, to acquire filtered minimizers;
• sub-step (3.5) reading, by the seed finder, the filtered minimizers output by the read length traverser to obtain unfiltered minimizers;
• sub-step (3.6) querying, by the seed finder, a seed position of the unfiltered minimizers and a reference sequence information of the seed position of the unfiltered minimizers from the index table;
• and
• sub-step (3.7) generating, by the seed finder, the reference subgraph according to the seed position of the unfiltered minimizes and the reference sequence information of the seed position of the unfiltered minimizers acquired in the sub-step (3.6), and identifying the candidate mapping position according to the reference subgraph to filter the candidate mapping area;
• and
• step (4) alignment:
• running approximate string matching between the read length and all unfiltered candidate mapping positions by adopting a Process-Using-Memory (PUM) mode, so as to achieve an optimal alignment of a reference gene sequence and a query gene sequence.