Systems and methods for genomic pattern analysis
The invention provides methods for analyzing sequence data in which a large amount and variety of reference data are efficiently modeled as a reference graph, such as a directed acyclic graph (DAG). The method includes determining positions of k-mers within a reference graph that represents a genomic sequence and known variation, storing the positions of each k-mer in a table entry indexed by a hash of that k-mer, and identifying a region within the reference graph that includes a threshold number of the k-mers by reading from the table entries indexed by hashes of substrings of a subject sequence. The subject sequence may subsequently be mapped to the candidate region.
1. A method for analyzing a genetic sequence, the method comprising:
obtaining a 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 graph, wherein at least one path through the graph represents substantially an entire chromosome;
identifying a data string for each path of the plurality of paths through the graph, each data string representing a concatenation of the substrings of genomic sequence and known variation in the genomic sequence stored in objects through the path;
for each data string:
identifying a plurality of k-mers in the data string; and
listing 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 locations of all k-mers having that index;
obtaining a query sequence;
identifying a plurality of query k-mers from the query sequence;
determining the locations of at least one query k-mer within the graph by reading search index entries indexed according to hashes of query k-mers; and
identifying portions of the 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 query sequence.
2. The method of claim 1 , wherein the query sequence is from a subject organism.
3. The method of claim 1 , wherein identifying a plurality of query k-mers from the query sequence further comprises identifying a plurality of query k-mers for the reverse complement of the query sequence.
4. The method of claim 1 , wherein each entry of the search index comprises an ordered list of locations for that indexed k-mer.
5. The method of claim 1 , wherein each k-mer comprises a sequence of symbols with fixed length k.
6. The method of claim 5 , wherein the fixed length k is within an interval [8, 14].
7. The method of claim 1 , wherein listing each k-mer's location within the graph further comprises excluding locations identified in a previous path.
8. The method of claim 1 , wherein the locations comprise floating point projections for alternate branches.
9. The method of claim 1 , wherein sub strings are stored in edge objects connected to one another by vertex objects to form a plurality of paths through the graph.
10. The method of claim 1 , further comprising identifying a best-fit location of the query sequence to the graph by performing a local alignment of the query sequence to each candidate target.
11. The method of claim 10 , wherein performing a local alignment comprises using a multidimensional Smith-Waterman algorithm.
12. The method of claim 1 , wherein the query sequence is a non-contiguous query.
13. The method of claim 12 , wherein the non-contiguous query comprises a pair of paired-end sequence reads.
14. The method of claim 13 , further comprising identifying portions of the graph in which the number of potential matches with different query k-mers is equal to or exceeds a threshold number within a window of ordered locations.
15. The method of claim 14 , wherein the window has a size that is less than 1000 base pairs.
16. The method of claim 1 , wherein the chromosome is a human chromosome.
17. 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 paired-end sequence read comprising a 5′ sequence read and a 3′ sequence read; and
determine candidate targets for alignment of the sequence read by:
identifying a plurality of query k-mers from the 5′ sequence read and the 3′ 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 wherein the identifying comprises:
creating a global ordering of locations corresponding to query k-mers from the 5′ sequence read and the 3′ sequence read; and
identifying locations in the global ordering in which both the 5′ sequence read and 3′ sequence read have query k-mers within a window.
18. The system of claim 17 , wherein the window has a size less than 1000 base pairs.
19. A method for analyzing a genetic sequence, the method comprising:
obtaining a 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 graph, wherein at least one path through the graph represents substantially an entire genome;
identifying a data string for each path of the plurality of paths through the graph, each data string representing a concatenation of the substrings of genomic sequence and known variation in the genomic sequence stored in objects through the path;
for each data string:
identifying a plurality of k-mers in the data string; and
listing 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 locations of all k-mers having that index;
obtaining a query sequence;
identifying a plurality of query k-mers from the query sequence;
determining the locations of at least one query k-mer within the graph by reading search index entries indexed according to hashes of query k-mers; and
identifying portions of the 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 query sequence.
20. The method of claim 19 , wherein substrings are stored in edge objects connected to one another by vertex objects to form a plurality of paths through the graph.