Systems and methods for genomic pattern analysis

A system for analyzing a genetic sequence, the system comprising:

• a tangible memory subsystem storing:
• a reference graph, the reference graph representing a genomic sequence and known variation in the genomic sequence, in which substrings of the genomic sequence and known variation are stored in objects connected to one another to form a plurality of paths through the reference graph;
• and
• a processor executing instructions configured to:
• identify a plurality of paths through the reference graph, each path representing a concatenation of the substrings of the genomic sequence and known variation in the genomic sequence stored in objects through the path;
• for each path of the plurality of paths, identify a plurality of k-mers in the path, and list each identified k-mer's location within the graph in an entry in a search index, wherein that entry is indexed according to a hash of that k-mer and contains an ordered list of locations of all k-mers having that index;
• receive a sequence read;
• and
• determine candidate targets for alignment of the sequence read by:
• identifying a plurality of query k-mers from the sequence read;
• determining the locations of each query k-mer within the reference graph by reading search index entries indexed according to hashes of query k-mers;
• and
• identifying portions of the reference graph in which a number of potential matches with different query k-mers is equal to or exceeds a threshold number as candidate targets within the graph for alignment of segments of the sequence read.