Systems and methods for aligning sequences to graph references

A system for aligning a sequence read to a graph reference, the system comprising:

• at least one computer hardware processor;
• and
• at least one non-transitory computer-readable storage medium storing:
• a graph reference, the graph reference comprising a plurality of nodes connected by a plurality of edges, at least one node of the plurality of nodes having an associated nucleotide sequence;
• a plurality of sequence reads;
• and processor-executable instructions that, when executed by the at least one computer hardware processor, cause the at least one computer hardware processor to perform:
• selecting a first node of the plurality of nodes;
• identifying a first path by traversing the graph reference, the first path starting from the first node and comprising at least one child node of the first node;
• comparing at least one first nucleotide sequence generated from the first path with the sequence read, wherein the at least one first nucleotide sequence is generated at least in part by concatenating associated nucleotide sequences from nodes in the first path into the at least one first nucleotide sequence;
• identifying a second path by traversing the graph reference, the second path starting from the first node and comprising at least one node not considered by the first path;
• comparing at least one second nucleotide sequence generated from the second path with the sequence read, the comparing comprising determining whether the at least one second nucleotide sequence generated from the second path was previously generated by the first path, and removing one or more nodes from the identified second path based on the determination;
• determining a best-fit position of the sequence read on the graph reference;
• and
• reporting the best-fit position of the sequence read as the aligned position of the sequence read on the graph reference.