SYSTEMS AND METHODS FOR ALIGNING SEQUENCES TO GRAPH REFERENCES
First Claim
1. 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;
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 has not been previously generated by the first path;
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.
6 Assignments
0 Petitions
Accused Products
Abstract
Various embodiments of the disclosure relate to systems and methods for aligning a sequence read to a graph reference. In one embodiment, the method comprises selecting a first node from a graph reference, the graph reference comprising a plurality of nodes connected by a plurality of directed edges, at least one node of the plurality of nodes having a nucleotide sequence. The method further comprises traversing the graph reference according to a depth-first search, and comparing a sequence read to nucleotide sequences generated from the traversal of the graph reference. The traversal of the graph is then modified in response to a determination that each and every node associated with a given nucleotide sequence was previously evaluated.
-
Citations
21 Claims
-
1. 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; 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 has not been previously generated by the first path; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21-32. -32. (canceled)
Specification